[알고리즘] 백준 2146 다리만들기

www.acmicpc.net/problem/2146

2146번: 다리 만들기

 

아이디어를 생각 해내면 그렇게 어렵지는 않은 문제같다... 물론.. 생각해내면..

 

입력으로 지도의 2차원 배열 정보가 주어진다.

 

BFS를 통해서 한 섬에서 다른 섬을 이어주는 최소비용을 구해야한다.

 

이 문제를 풀기 위해서는 섬과 바다가 맞닿아있는 지점을 반복문을 통해 BFS를 돌려 최소의 거리를 찾아야한다.

 

여기까지는 어렵지 않게 생각을 했긴 하지만, 해당 지점이 섬과 맞닿아있는지 판별하는 것과 다른 섬에 도착하여 BFS를 멈춰야 하는데 그 조건을 어떻게 걸어줄 것인가... 를 생각하는데 좀 시간이 많이 걸렸다.

 

먼저 BFS를 멈추는 조건은 섬마다 숫자를 붙임으로써 해결하였다. (얘 때문에 이 문제는 BFS를 2번 돌려야함)

 

BFS를 시작한 좌표의 섬과 달라지면! return하도록 했다.

 

그 다음으로 해당 지점이 섬과 맞닿아있는지를 판별하기 위해 나는 아래와 같이 했다.

    // 좌표와 바다가 맞닿아있는가
    static boolean isEdge(int x, int y) {

        // 0이면 바다
        if (map[x][y] == 0) {
            return false;
        }

        // map[nx][ny]가 바다면 맞닿아있는거임
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                if (map[nx][ny] == 0) {
                    return true;
                }
            }
        }
        
        return false;
    }

 

이럼 다 됐겠다 하고 바다와 맞닿아있는 지점을 모두 BFS를 돌렸는데 메모리가 터졌다.

 

그래서 생각해낸 방법은 반복문을 통해 해변에서 계속 BFS를 타면 필연적으로 방문했던 곳을 계속 큐에 넣게될텐데 큐에 넣는 횟수를 줄여보자는 것이였다.

 

문제와 BFS를 잘 이해하고 있다면 현재 시점에 내가 방문하고자 하는 지점의 cost값 보다 이전에 넣어줬던 cost값이 더 작다면 현재 시점에 방문하고자 하는 지점을 큐에 넣지 않아도 될 것이라는 사실을 이해할 수 있을 것이다.

 

그리하여 입력으로 주어진 배열 내에서 cost값을 처리하려고 했으나 그리하면 로직이 많이 복잡해지기 때문에 cost값만 넣어지게 되는 distance[][]를 새로 만들어 사용하였다.

 

소스코드

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

class Main {
    static int n;
    static int[][] map;
    static int[][] distance;
    static boolean[][] visited;

    static final int[] dx = {0, 0, -1, 1};
    static final int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        n = Integer.parseInt(s);
        map = new int[n][n];
        visited = new boolean[n][n];
        distance = new int[n][n];

        for (int i = 0; i < n; i++) {
            s = br.readLine();
            StringTokenizer st = new StringTokenizer(s, " ");

            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // input end

        // 섬 이름 붙여주기
        int section = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    searchSection(new Location(i, j, 0), section);
                    section++;
                }
            }
        }
        // 섬 이름 붙여주기 끝

        // 거리 나타내는 배열초기화
        for (int i = 0; i < n; i++) {
            Arrays.fill(distance[i], Integer.MAX_VALUE);
        }

        // 결과값 계산
        int result = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (isEdge(i, j)) {
                    result = Math.min(calDistance(new Location(i, j, 0)), result);
                }
            }
        }

        System.out.println(result);
    }

    // 섬 이름 붙여주기
    static void searchSection(Location location, int section) {
        Queue<Location> queue = new LinkedList<>();
        queue.add(location);
        visited[location.x][location.y] = true;
        map[location.x][location.y] = section;

        while (!queue.isEmpty()) {
            Location currentLocation = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = currentLocation.x + dx[i];
                int ny = currentLocation.y + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    if (map[nx][ny] != 0 && !visited[nx][ny]) {
                        queue.add(new Location(nx, ny, 0));
                        visited[nx][ny] = true;
                        map[nx][ny] = section;
                    }
                }
            }
        }
    }

    // 거리 계산
    static int calDistance(Location location) {
        Queue<Location> queue = new LinkedList<>();
        queue.add(location);
        int result = Integer.MAX_VALUE;

        while (!queue.isEmpty()) {
            Location current = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = current.x + dx[i];
                int ny = current.y + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                    if (map[nx][ny] == 0 && !visited[nx][ny]) {
                        // 방문하지 않아도 되는 경우 예외처리
                        // 이전에 갔던 루트가 더 쌀 경우에는 큐에 넣지 않음
                        if (current.value + 1 < distance[nx][ny]) {
                            queue.add(new Location(nx, ny, current.value + 1));
                            distance[nx][ny] = current.value + 1;
                        }
                    }

                    // 다른 섬에 도착하면 bfs 종료
                    if ((map[nx][ny] != map[location.x][location.y]) && map[nx][ny] != 0) {
                        return current.value;
                    }
                }
            }
        }
        // 도달할 수 없는 경우 Integer.MAX_VALUE
        return result;
    }

    // 좌표와 바다가 맞닿아있는가
    static boolean isEdge(int x, int y) {

        // 0이면 바다
        if (map[x][y] == 0) {
            return false;
        }

        // map[nx][ny]가 바다면 맞닿아있는거임
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                if (map[nx][ny] == 0) {
                    return true;
                }
            }
        }

        return false;
    }

    static class Location {
        int x;
        int y;
        int value;

        public Location(int x, int y, int value) {
            this.x = x;
            this.y = y;
            this.value = value;
        }
    }

}