kingsubin

import java.io.*;
import java.util.*;
 
public class boj_2146 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Queue<int[]> q = new LinkedList<>();
    static boolean[][] v;
    static int[][] a, map;
    static int ans = Integer.MAX_VALUE;
    static int N, islandCnt, nx, ny;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
 
    public static void main(String[] args) throws IOException {
        input(); 
        createMap();
        findDistance();
        System.out.println(ans);
    }
 
    static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
 
        a = new int[N][N];
        map = new int[N][N];
        v = new boolean[N][N];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
 
    static void createMap() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (a[i][j] == 1 && !v[i][j]) {
                    islandCnt++;
                    map[i][j] = islandCnt;
                    v[i][j] = true;
                    q.offer(new int[] {i, j});
 
 
                    while (!q.isEmpty()) {
                        int[] now = q.poll();
                        for (int k = 0; k < 4; k++) {
                            nx = now[0] + dx[k];
                            ny = now[1] + dy[k];
 
                            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                            if (!v[nx][ny] && a[nx][ny] == 1) {
                                map[nx][ny] = islandCnt;
                                v[nx][ny] = true;
                                q.offer(new int[]{nx, ny});
                            }
                        }
                    }
                }
            }
        }
    }
 
    static boolean isEdge(int i, int j) {
        for (int k = 0; k < 4; k++) {
            nx = i + dx[k];
            ny = j + dy[k];
 
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (map[nx][ny] == 0) return true;
        }
 
        return false;
    }
 
    static void findDistance() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                
                // 섬이면서 바다와 인접한 경우만 탐색이 필요 
                if (map[i][j] != 0 && isEdge(i, j)) {
                    v = new boolean[N][N];
                    q.offer(new int[] {i, j, 0});
                    int landNum = map[i][j];
 
                    while (!q.isEmpty()) {
                        int[] now = q.poll();
                        int dist = now[2];
 
                        for (int k = 0; k < 4; k++) {
                            nx = now[0] + dx[k];
                            ny = now[1] + dy[k];
                            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                            
                            // 다른 섬 발견 
                            if (map[nx][ny] != 0 && map[nx][ny] != landNum) {
                                ans = Math.min(ans, dist);
                            }
 
                            // 바다일 경우 
                            if (map[nx][ny] == 0 && !v[nx][ny]) {
                                v[nx][ny] = true;
                                q.offer(new int[] {nx, ny, dist + 1});
                            }
                        }
                    }
                }
            }
        }
    }
}
 

 

- 1차 실패

 

- 오래 걸려서 근접했으나 아쉽다.

- 메소드가 한 가지 일만 하도록 세분화 시키자.

- 할 수 있는거도 복잡하니까 더 어려워진다.

 

1. 입력 받은후 섬에서 다른섬이랑 구분이 어려움 -> createMap 으로 각자 섬마다 고유 번호를 붙여줌

2. 탐색을 돌때 섬의 모든 부분에서 돌 필요 없이 바다와 인접해있는 부분에서만 돌면됨 -> isEdge 로 판별

3. findDistance로 탐색 시작

-> 각 부분에서 방문체크 필요한 v 새로 생성

-> 다른 섬 발견 했을경우 ans를 최솟값으로 수정

-> 바다일경우에는 계속 dist 증가

 

 

---

www.acmicpc.net/problem/2146