[골드3, BFS] 백준 2146 - 다리 만들기 (자바)

Think

1. 문제를 처음 읽고나서 생각한 풀이는, 섬 가장자리 위치를 큐에 모두 저장하고, BFS를 한번에 돌리면 되겠다고 생각했다.
2. 하지만, 가장자리 포인트들에서 동시에 BFS가 돌아가다보니, 거리가 상쇄가 되어버렸다. (거리가 4라면 2로 되어버림)
3. 어떻게 풀지 계속 고민하다가 구글링을 했다. (https://todaycode.tistory.com/166)
4. 풀이 방식은 이렇다.
   1. 각 섬들을 넘버링한다. (다른 섬의 경계에 도착했는지 체크하기 위함, 1로만 되어있는 섬 표식을 2,3,4로 표시 (2부터 넘버링하는게 더 편함))
   2. 2중 for문을 돌면서 BFS를 시도한다.
      • map[nextR][nextC] ≠ 0 이면, 섬 가장자리가 아니라는 의미이기 때문에 BFS를 진행하지 않는다. (다른 if문으로 인해 자동으로 걸러짐)
      • map[nextR][nextC] == 0 이면, BFS 진행
      • map[nextR][nextC] ≠ islandNumber 이면, 다른 섬에 도착했다는 의미 (최소 거리 체크 하기)
      • q.add(new int[]{r,c,0}); 와 같이, distance를 큐에 같이 넣어주기
      • if(position[2] >= *minDistance*) continue; 조건을 통해 가지치기 진행 (속도 차이 6배정도..)

 

 

 

정답 코드

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

public class test {
    static int N, map[][], minDistance = Integer.MAX_VALUE;
    static boolean isVisited[][];
    static int[] dr = new int[]{0, 0, 1, -1};
    static int[] dc = new int[]{1, -1, 0, 0};
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        init();

        process();

        System.out.println(minDistance);
    }

    private static void process() {

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(map[i][j] != 0){
                    bfs(i,j, map[i][j]);
                }
            }
        }

    }

    private static void bfs(int r, int c, int islandNumber) {
        Deque<int[]> q = new ArrayDeque<>();

        isVisited = new boolean[N][N];

        isVisited[r][c] = true;
        q.add(new int[]{r,c,0});

        while (!q.isEmpty()) {
            int[] position = q.poll();
            if(position[2] >= minDistance) continue;

            for (int i = 0; i < 4; i++) {
                int mr = position[0] + dr[i];
                int mc = position[1] + dc[i];
                int mDistance = position[2] + 1;

                if (mr < 0 || mc < 0 || mr >= N || mc >= N || isVisited[mr][mc]) continue;

                if(map[mr][mc] == 0){
                    q.add(new int[]{mr, mc, mDistance});
                    isVisited[mr][mc] = true;
                }else if(map[mr][mc] != islandNumber){
                    minDistance = Math.min(minDistance, mDistance - 1);
                }
            }
        }
    }

    private static void init() throws IOException {
        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());
            }
        }

        int labelNumber = 2;

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

    private static void islandLabelingBFS(int r, int c, int labelNumber) {
        Deque<int[]> q = new ArrayDeque<>();

        isVisited = new boolean[N][N];
        isVisited[r][c] = true;
        map[r][c] = labelNumber;

        q.add(new int[]{r,c});

        while (!q.isEmpty()) {
            int[] position = q.poll();

            for (int i = 0; i < 4; i++) {
                int mr = position[0] + dr[i];
                int mc = position[1] + dc[i];

                if (mr < 0 || mc < 0 || mr >= N || mc >= N || isVisited[mr][mc] || map[mr][mc] == 0) continue;

                map[mr][mc] = labelNumber;
                q.add(new int[]{mr, mc});
                isVisited[mr][mc] = true;
            }
        }
    }
}

처음 시도했다가 틀린 코드

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

public class test {
    static int N, map[][], distanceMap[][], minDistance = Integer.MAX_VALUE;
    static LinkedList<int[]> boundaryLands = new LinkedList<>();
    static Deque<int[]> q = new ArrayDeque<>();
    static Deque<int[]> distanceQ = new ArrayDeque<>();
    static boolean isVisited[][];
    static int[] dr = new int[]{0, 0, 1, -1};
    static int[] dc = new int[]{1, -1, 0, 0};
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        init();

        process();

        for (int i = 0; i < N; i++) {
            System.out.println(Arrays.toString(distanceMap[i]));
        }
        System.out.println(minDistance);
    }

    private static void process() {
        bfs();

        for(int[] p : boundaryLands){
            minDistance = Math.min(distanceMap[p[0]][p[1]], minDistance);
        }
    }

    private static void bfs() {

        isVisited = new boolean[N][N];
        int distance = 0;

        while(!q.isEmpty()){
            int qSize = q.size();
            for (int i = 0; i < qSize; i++) {
                int[] position = q.poll();
                isVisited[position[0]][position[1]] = true;

                for (int j = 0; j < 4; j++) {
                    int mr = position[0] + dr[j];
                    int mc = position[1] + dc[j];

                    if(mr<0 || mc<0||mr>=N || mc>= N || isVisited[mr][mc] || map[mr][mc] == 1)   continue;

                    q.add(new int[]{mr,mc});
                    distanceQ.add(new int[]{mr,mc});
                    isVisited[mr][mc] = true;
                }
            }

            distance++;

            while(!distanceQ.isEmpty()){
                int size = distanceQ.size();

                for (int i = 0; i < size; i++) {
                    int[] p = distanceQ.poll();
                    distanceMap[p[0]][p[1]] = distance;
                }
            }
        }
    }

    private static void init() throws IOException {
        N = Integer.parseInt(br.readLine());

        map = new int[N][N];
        distanceMap = 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());
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 섬 가장자리 부분을 찾아서 해당 r,c를 큐에 저장
                if(map[i][j] == 1){

                    for (int k = 0; k < 4; k++) {
                        int mr = i + dr[k];
                        int mc = j + dc[k];

                        if(mr<0 || mc<0||mr>=N || mc>= N)   continue;

                        if(map[mr][mc] == 0){
                            boundaryLands.add(new int[]{i,j});
                            q.add(new int[]{i,j});
                            break;
                        }
                    }
                }
            }
        }

    }

}