백준 2146. 다리 만들기 :: 돼지개발자

출저 : https://www.acmicpc.net/problem/2146

"BFS 두번"

각각의 섬들에 2부터 시작하는 넘버링을 한다. 이 과정은 BFS를 사용한다. 넘버링 까지는 쉽게 할 수 있다. 체크한 땅들에 대해서는 visited 배열을 통해 중복을 제거해준다. 그렇게 2 ~ .. 넘버링을 하였으면 이제 isEdge 함수를 활용해 각 섬의 모든 가장자리에서 시작해서 탐색을 시작하여 다른 섬을 만날 때 까지 탐색을 한다.

다른 섬을 구분하는 구문은 아래와 같다.

if(map[cur.x][cur.y] != idx && map[cur.x][cur.y] > 0) {

q.clear();

break loop;

} 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Main {
 
    static int N;
    static int[][] map;
    static boolean[][] visited;
    static Queue<Node> q = new LinkedList<>();
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    static int mark = 2;
    static int min = Integer.MAX_VALUE;
    
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        
        map = new int[N][N];
        visited = new boolean[N][N];
        
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        mark();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(map[i][j] == 0 || !isEdge(i, j))
                    continue;
                visited = new boolean[N][N];
                
                int cnt = 0;
                int idx = map[i][j];
                
                visited[i][j] = true;
                q.add(new Node(i, j));
                
                loop: while(!q.isEmpty()) {
                    int size = q.size();
                    
                    for (int s = 0; s < size; s++) {
                        
                        Node cur = q.poll();
                        
                        if(map[cur.x][cur.y] != idx && map[cur.x][cur.y] > 0) {
                            q.clear();
                            break loop;
                        }
                        
                        for (int k = 0; k < 4; k++) {
                            int nx = cur.x + dx[k];
                            int ny = cur.y + dy[k];
                            
                            if(!isRange(nx, ny) || visited[nx][ny] || map[nx][ny] == idx) 
                                continue;
                            
                            visited[nx][ny] = true;
                            q.add(new Node(nx, ny));
                        }
                        
                    }
                    cnt++;
                }
                min = Math.min(min, cnt-1);
            }
        }
        System.out.println(min);
        
    }
    
    static boolean isEdge(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(!isRange(nx,ny) || map[nx][ny] != 0) continue;
            return true;
        }
        return false;
    }
    
    static void mark() {
        
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(map[i][j] != 1) continue;
                
                map[i][j] = mark;
                q.add(new Node(i, j));
                
                while(!q.isEmpty()) {
                    Node cur = q.poll();
                    
                    for (int k = 0; k < 4; k++) {
                        int nx = cur.x + dx[k];
                        int ny = cur.y + dy[k];
                        
                        if(!isRange(nx, ny) || map[nx][ny] != 1) continue;
                        
                        map[nx][ny] = mark;
                        q.add(new Node(nx, ny));
                    }
                }
                mark++;
            }
        }
    }
    
    static boolean isRange(int x, int y) {
        if( x < 0 || x >= N || y < 0 || y >= N) return false;
        return true;
    }
 
}
 
class Node {
    int x;
    int y;
    
    Node (int x, int y) {
        this.x = x;
        this.y = y;
    }
}