[BOJ] 2146: 다리 만들기 (JAVA)

문제

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

 

여담

전에 풀었을 때는 맞았었는데 이번에는 틀렸다 ^^...

 

각각의 육지에서 탐색을 해야 하는데 한 섬에서 최단 거리의 다리를 찾는 방식으로 수행했었다. 그렇게 하면 최단 거리를 기록하는데 오류가 생기기 때문에 올바른 답이 나오지 않는 것이었다.. 잘 생각해 보면 당연히 틀린 풀이인데 검증하지 않고 무작정 코딩을 해서 그런 것 같다.. ㅜㅜ

 

풀이

섬 사이의 최단 거리를 구하기 위해 BFS 탐색을 수행하면 된다.

 

우선 섬들이 모두 1로 주어지기 때문에, BFS 탐색을 통해 각 섬을 구분해야 한다. 

 

그 후, 각각의 좌표에서 ((0, 0) ~ (N - 1, N - 1)) BFS 탐색을 수행해서 다른 섬에 도착하는 경우에만 최단 거리를 갱신하면 된다.

 

전체 풀이 과정을 정리하면 다음과 같다.

1. 각 섬을 구분하기
2. map[i][j]의 값이 0이 아닌 곳(= 섬)에서 BFS 탐색을 수행해서 다른 섬까지의 최단 거리 구하기
   • 다음에 탐색할 곳이 바다인 경우 바다인 경우
     • 큐에 넣고 방문 처리하기
     • 거리 기록하기: dist[nx][ny] = dist[x][y] + 1
   • 다음에 탐색할 곳이 다른 섬인 경우
     
     • 섬 사이의 최단 거리를 갱신하기: minDist = Math.min(minDist, dist[x][y])
     • 두 섬을 연결하는 최단 거리를 찾았으므로, 탐색을 종료하기

 

코드

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

public class Main {
    static int N, minDist = Integer.MAX_VALUE;
    static int[][] map, dist;
    static boolean[][] visited;
    static int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        dist = 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());
            }
        }

        // 그룹 나누기
        int group = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1) {
                    makeGroup(i, j, ++group);
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] != 0) {
                    visited = new boolean[N][N];
                    dist = new int[N][N];
                    bfs(i, j);
                }
            }
        }
        System.out.println(minDist);
    }

    static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;

        int group = map[x][y];
        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            x = now[0]; y = now[1];

            // 현재 최소 길이보다 길면 최소 거리가 되지 않으므로 탐색 중단
            if (dist[x][y] > minDist) break;
            for (int i = 0; i < 4; i++) {
                int nx = x + move[i][0];
                int ny = y + move[i][1];
                // 범위 벗어나거나 이미 방문했거나 같은 섬을 탐색하려고 하는 경우라면 그냥 넘어가기
                if (nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny] || map[nx][ny] == group) {
                    continue;
                }

                if (map[nx][ny] == 0) { // 바다인 경우
                    queue.offer(new int[]{nx, ny});
                    visited[nx][ny] = true;
                    dist[nx][ny] = dist[x][y] + 1;
                } else if (map[nx][ny] != map[x][y]) { // 다른 섬에 닿은 경우
                    minDist = Math.min(minDist, dist[x][y]);
                    break;
                }
            }
        }
    }

    static void makeGroup(int x, int y, int group) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;
        map[x][y] = group;

        while (!queue.isEmpty()) {
            int[] now = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = now[0] + move[i][0];
                int ny = now[1] + move[i][1];
                if (nx < 0 || ny < 0 || nx >= N || ny >= N || map[nx][ny] == 0) {
                    continue;
                }

                if (map[nx][ny] == 1) {
                    map[nx][ny] = group;
                    queue.offer(new int[]{nx, ny});
                }
            }
        }
    }
}

---