[Java] 백준 2146 다리만들기

 

 

문제 설명

섬과 바다가 있는 지도가 주어진다.

섬과 또 다른 섬을 잇는 다리를 만든다고 할 때, 가장 짧은 다리의 길이를 출력하라.

 

 

풀이

각 섬을 그룹화하여 번호를 붙이는 것은 어렵지 않았지만, 최단경로를 구하는 부분에서 어려움이 있었다.

최단경로를 구하는 메서드의 로직을 처음 푼 방식과 추후 수정한 방식 2가지로 정리해보았다.

 

 

1. (처음 푼 방식) 섬 1개를 기준으로 탐색하여 다른 섬을 발견하면 탐색을 멈추는 방식

 

- 최단경로를 구하기 위해서 이동거리를 담을 배열 visited를 Integer.MAX_VALUE로 초기화한다.

int[][] visited = new int[N][N];
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        visited[i][j] = Integer.MAX_VALUE;
    }
}

 

- 주어진 map을 처음부터 탐색하여 섬인 좌표가 발견되면 해당 섬을 기준으로 최단거리를 탐색한다. 

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (map[i][j] == SEA) continue;

        int GROUPNUM = map[i][j]; // 현재 섬의 번호
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});
        visited[i][j] = 0;

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

            for (int k = 0; k < 4; k++) {
                int nx = point[0] + dx[k];
                int ny = point[1] + dy[k];

                // 섬
                if (isRange(nx, ny) && map[nx][ny] != SEA) {
                    // 같은 섬이고, 아직 방문 안했으면
                    if (map[nx][ny] == GROUPNUM && visited[nx][ny] != 0) {
                        visited[nx][ny] = 0;
                        queue.add(new int[]{nx, ny});
                    }
                    // 다른 섬이면서 현재경로가 최단경로보다 짧으면
                    if (map[nx][ny] != GROUPNUM
                            && visited[nx][ny] > visited[point[0]][point[1]]) {
                        shortest = Math.min(shortest, visited[point[0]][point[1]]);
                    }
                }

                // 바다면서 현재경로가 최단경로보다 짧으면
                if (isRange(nx, ny) && map[nx][ny] == SEA
                        && visited[nx][ny] > visited[point[0]][point[1]] + 1) {
                    visited[nx][ny] = visited[point[0]][point[1]] + 1;
                    queue.add(new int[]{nx, ny});
                }
            }
        }// end of while

    }
}// end of for

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N, SEA = 0, LAND = 1;
    static int[][] map;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    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];

        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());
            }
        }

        mkGroup();
        System.out.println(getShortest());
    }

    static int getShortest() {
        int shortest = Integer.MAX_VALUE;

int[][] visited = new int[N][N];
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        visited[i][j] = Integer.MAX_VALUE;
    }
}

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == SEA) continue;

                int GROUPNUM = map[i][j]; // 현재 섬의 번호
                Queue<int[]> queue = new LinkedList<>();
                queue.add(new int[]{i, j});
                visited[i][j] = 0;

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

                    for (int k = 0; k < 4; k++) {
                        int nx = point[0] + dx[k];
                        int ny = point[1] + dy[k];

                        // 섬
                        if (isRange(nx, ny) && map[nx][ny] != SEA) {
                            // 같은 섬이고, 아직 방문 안했으면
                            if (map[nx][ny] == GROUPNUM && visited[nx][ny] != 0) {
                                visited[nx][ny] = 0;
                                queue.add(new int[]{nx, ny});
                            }
                            // 다른 섬이면서 현재경로가 최단경로보다 짧으면
                            if (map[nx][ny] != GROUPNUM
                                    && visited[nx][ny] > visited[point[0]][point[1]]) {
                                shortest = Math.min(shortest, visited[point[0]][point[1]]);
                            }
                        }

                        // 바다면서 현재경로가 최단경로보다 짧으면
                        if (isRange(nx, ny) && map[nx][ny] == SEA
                                && visited[nx][ny] > visited[point[0]][point[1]] + 1) {
                            visited[nx][ny] = visited[point[0]][point[1]] + 1;
                            queue.add(new int[]{nx, ny});
                        }
                    }
                }// end of while

            }
        }// end of for

        return shortest;
    }

    static void mkGroup() {
        int groupNum = 1;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] != LAND) continue;

                Queue<int[]> queue = new LinkedList<>();
                queue.add(new int[]{i, j});
                map[i][j] = ++groupNum;

                while (!queue.isEmpty()) {
                    int[] point = queue.poll();
                    for (int k = 0; k < 4; k++) {
                        int nx = point[0] + dx[k];
                        int ny = point[1] + dy[k];
                        if (isRange(nx, ny) && map[nx][ny] == LAND) {
                            queue.add(new int[]{nx, ny});
                            map[nx][ny] = groupNum;
                        }
                    }
                }// end of while

            }
        }// end of for

    }// end of mkGroup()

    static boolean isRange(int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= N)
            return false;
        return true;
    }
}

 

코드가 통과하긴 했지만, 다른 사람들의 풀이에 비해서 속도와 메모리의 차이가 났다.

다른 분들의 풀이를 참고한 결과, 내가 짠 것처럼 한 섬을 기준으로 다른 섬을 탐색하는 방식이 아니라

모든 섬들이 동시에 움직이며 탐색하는 방식이 훨씬 효율적이라는 것을 깨달았다. 

해당 방식으로 한번 더 풀어봤다.

 

 

2. (다시 푼 방식) 모든 섬을 함께 탐색하여 자신의 섬 번호와 다른 섬을 발견하면 탐색을 멈추는 방식

 

- 입력받을 때부터, 섬의 좌표를 모두 queue에 삽입해 놓는다.

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());
        if (map[i][j] == LAND) queue.add(new int[]{i, j}); // 섬의 좌표 queue에 추가
    }
}

 

- 최단경로를 탐색할 때, 탐색한 좌표의 값이 0(SEA)이면 해당 좌표의 map값을 현재 섬의 번호로 초기화한다.

if (isRange(nx, ny) && map[nx][ny] == SEA) {
    map[nx][ny] = map[curr[0]][curr[1]]; // 현재 섬의 번호로 map값 초기화
    visited[nx][ny] = visited[curr[0]][curr[1]] + 1; // 현재 이동횟수로 visited값 초기화
    queue.add(new int[]{nx, ny});
}

 

- 탐색한 좌표의 값이 0(SEA)가 아니며, 현재 탐색의 기준이 되는 섬과 다른 섬이면 현재 좌표의 visited값(이동거리)와 탐색한 좌표의 visited값을 더한 값과 최단경로의 값을 비교하여 최단경로를 초기화한다.

else if (isRange(nx, ny) && map[nx][ny] != map[curr[0]][curr[1]]) {// 현재 섬과 다른 섬이면
    shortest = Math.min(shortest, visited[nx][ny] + visited[curr[0]][curr[1]]); // 최단거리 비교
}

 

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static int N, SEA = 0, LAND = 1;
    static int[][] map;
    static Queue<int[]> queue;

    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];
        queue = new LinkedList<>();

        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());
                if (map[i][j] == LAND) queue.add(new int[]{i, j});
            }
        }

        mkGroup();
        System.out.println(getShortest());
    }

    static int getShortest() {
        int shortest = Integer.MAX_VALUE;
        int[][] visited = new int[N][N];

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = curr[0] + dx[i];
                int ny = curr[1] + dy[i];
                // 바다일 때
            if (isRange(nx, ny) && map[nx][ny] == SEA) {
                map[nx][ny] = map[curr[0]][curr[1]];
                visited[nx][ny] = visited[curr[0]][curr[1]] + 1;
                queue.add(new int[]{nx, ny});
            }
                // 다른 섬일 때
                else if (isRange(nx, ny) && map[nx][ny] != map[curr[0]][curr[1]]) {
                    shortest = Math.min(shortest, visited[nx][ny] + visited[curr[0]][curr[1]]);
                }
            }
        }

        return shortest;
    }

    static void mkGroup() {
        int groupNum = 1;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] != LAND) continue;

                Queue<int[]> queue = new LinkedList<>();
                queue.add(new int[]{i, j});
                map[i][j] = ++groupNum;
                while (!queue.isEmpty()) {
                    int[] point = queue.poll();
                    for (int k = 0; k < 4; k++) {
                        int nx = point[0] + dx[k];
                        int ny = point[1] + dy[k];
                        if (isRange(nx, ny) && map[nx][ny] == LAND) {
                            queue.add(new int[]{nx, ny});
                            map[nx][ny] = groupNum;
                        }
                    }
                }
            }
        }
    }

    static boolean isRange(int x, int y) {
        if (x < 0 || x >= N || y < 0 || y >= N)
            return false;
        return true;
    }
}

 

 

채점결과 (아래: 1번째 방법, 위: 2번째 방법)