[백준 Gold 3] 2146 다리 만들기 - Java

문제링크 : https://www.acmicpc.net/problem/2146

2146번: 다리 만들기

 

접근 과정 : 

• DFS를 통해 같은 대륙은 같은 번호를 붙여서 구분.
• 대륙을 탐색할 때, 대륙은 Queue에 좌표와 대륙 번호를 저장 (BFS 때 이용하기 위해)
• 어떤 대륙에서 출발하여, 다른 번호의 대륙을 만날 때, 그 거리를 반환하는 BFS 구성
• 한칸에서 시작하는 DFS를 하는 것이 아니라, 모든 대륙을 담은 Queue로 한번에 BFS를 시행
• 방문체크는 int[][]에 비트마스킹을 통해 시행 -> 해당 좌표에 대륙번호가 포함되어 있으면 이미 방문한 곳. 

 

소스 코드 및 결과 :

package BOJ;

/* 
    다리 만들기

*/

import java.io.*;
import java.util.*;

public class BOJ2146 {

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        numbering();

        int distance = bridge();

        System.out.println(distance);

    }

    static int N;
    static int[][] map;
    static int[][] d = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    static Queue<int[]> queue;

    static void findIsland(int r, int c, int num) {

        map[r][c] = num;
        queue.add(new int[] { r, c, num });

        for (int i = 0; i < 4; i++) {
            int nr = r + d[i][0];
            int nc = c + d[i][1];

            if (nr < 0 || nr >= N || nc < 0 || nc >= N || map[nr][nc] != 1) {
                continue;
            }

            findIsland(nr, nc, num);
        }

    }

    static void numbering() {
        queue = new LinkedList<>();

        int num = 2;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1) {
                    findIsland(i, j, num++);
                }
            }
        }
    }

    static int bridge() {

        int[][] visit = new int[N][N];

        int count = 0;

        loop: while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int[] now = queue.poll();

           
                for (int i = 0; i < 4; i++) {
                    int nr = now[0] + d[i][0];
                    int nc = now[1] + d[i][1];

                    if (nr < 0 || nr >= N || nc < 0 || nc >= N) {
                        continue;
                    }

                    if (map[nr][nc] == now[2]) {
                        continue;
                    }
                    if ((visit[nr][nc] | (1 << now[2])) == visit[nr][nc]) {
                        continue;
                    }
                    visit[nr][nc] |= 1 << now[2];

                    if (map[nr][nc] != 0) {
                        break loop;
                    }
                    queue.add(new int[] { nr, nc, now[2] });
                }
            }

            count++;
        }

        return count;
    }
}

 

P.S 

대륙 한칸씩 출발점을 정하는 DFS보다는 한번에 시행하는 BFS가 더 빠를 것이라 생각했다.

방문체크가 힘든 부분 (다른 대륙에서 출발했는데 같은 곳을 방문한 경우) 를 비트마스킹을 통해 해결.

다른 좋은 방법이 있다면 어떤 것인지 궁금하다..