BOJ - 다리 만들기 2146번 (JAVA)

❓ 문제 - 백준 다리 만들기 2146번 - JAVA 풀이법

 

출처

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

2146번: 다리 만들기

 

 

📝 문제해결법

1. 문제

• N*N 크기의 이차원 평면상에 여러 개의 섬으로 이루어져 있는데 각 섬을 바다 위에 놓을 수 있다.
• 두 대륙을 잇는 가장 짧은 다리의 길이를 구하여라.

 

2. 해결 방법

• 우선 N의 크기가 (100이하의 자연수)이기 때문에 BFS나 DFS의 완전탐색 기법으로 이어진 섬을 분류하고 각 섬에서 다른 섬으로 다시 BFS나 DFS로 바다의 다리를 만들어가면서 다른 육지로 갈 수 있는 다리의 길이를 구한 뒤 최솟값을 갱신하면 된다.
• 만약 완전탐색 기법으로 BFS를 두 번 이용하면 첫 번째 섬을 구분할 때 N*N, 두 번째 다리를 연결할 때 섬의 최대갯수(N)*N*N 정도여서 시간안에 통과 가능하다.
• 두 번째 각 섬에서 바다에 다리를 놔서 다른 섬까지 이어지는 다리의 길이를 구할 때는 4방 탐색으로 바다일 경우 다리의 길이를 늘리고 만약 다른 섬이라면 다리가 끝나므로 지금까지 구한 다리의 길이를 갱신하도록 한다.
• 하지만 여기서 주의할 점은, boolean visited의 방문처리로만 이 다리 길이를 구하면  밑의 경우처럼 이미 방문되었지만 다리길이가 최소가 아닌데, 다른 최소의 길이로 해당 지역을 방문하면 이미 방문처리 되었기 때문에 탐색을 멈춘다. 따라서 최소의 다리 길이를 구할 수 없게 된다.  

10 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 => 여기서 답은 17이 나와야 함

• 따라서 두 번째 BFS 내에서 방문에 대한 것을 int[][] visited 2차원 배열로 관리한다.
• 그리고 만약 지나가려는데 바다라면 이미 방문하지 않은 경우나 현재 지금까지의 다리길이로 더 짧게 해당 지역에 다리를 건설할 수 있는 경우에만 q에 넣어 방문할 수 있도록 구현한다.
• 밑의 코드는 위의 설명을 나타나는 부분이다.

if(visited[nx][ny] == -1 || visited[nx][ny] > visited[node.x][node.y]+1){
    visited[nx][ny] = visited[node.x][node.y]+1;
    q.add(new Node(nx, ny));
}

 

 

 

 

3. 느낀점

• 구현 방법은 쉽게 떠올렸지만 시간초과랑 메모리 초과 둘 다 떠서 이틀동안 고민했던 것... 알고보니 시간초과는 dfs -> bfs로 바꾸고 방문처리에 대한 것을 boolean에서 int 2차원배열로 바꿔서 해결했다.
• 근데 그 뒤에 메모리 초과가 떠서 처음에 방문처리 2차원 배열이 너무 많이 생성돼서 그런가 하면서 계속 고민했는데 알고보니 queue에 너무 많은 값들이 들어가서 그런 것.. 그리고 visited[nx][ny] > visited[node.x][node.y]로 잘못 코딩해서 그랬다..^^
• 그래도 시초, 메초를 코드를 꾸준히 봐서 해결할 수 있어서 뿌듯하다.. 이제 이런 실수는 하지 말아야지!

 

 

💻 소스코드 (JAVA)

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;

public class Main {
    public static int n;
    public static int s;
    public static int[][] map;
    public static int[][] check;
    public static int min_value;

    public static class Node {
        int x;
        int y;
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        n = Integer.parseInt(br.readLine());
        s = 0;
        map = new int[n][n];
        check = 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());
            }
        }

        min_value = Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(check[i][j] == 0 && map[i][j] == 1){
                    bfs(i, j, ++s);
                }
            }
        }

        for(int i=1;i<=s;i++){
            bfs2(i);
        }

        System.out.println(min_value);
    }
	
    // 각 연결된 육지로 섬의 번호를 부여하는 bfs
    public static void bfs(int x, int y, int c){
        Queue<Node> q = new LinkedList<>();
        check[x][y] = c;
        q.add(new Node(x, y));
        while (!q.isEmpty()){
            Node node = q.poll();
            for(int d=0;d<4;d++){
                int nx = node.x + dx[d];
                int ny = node.y + dy[d];
                if(0 <= nx && nx < n && 0 <= ny && ny < n){
                    if(map[nx][ny] == 1){
                        if(check[nx][ny] == 0){
                            check[nx][ny] = c;
                            q.add(new Node(nx, ny));
                        }
                    }

                }
            }
        }
    }
	
    // 각 연결된 섬에서 다리를 놓는 bfs
    public static void bfs2(int c){
        Queue<Node> q = new LinkedList<>();
        int[][] visited = new int[n][n];
        for(int i=0;i<n;i++){
            Arrays.fill(visited[i], -1);
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(check[i][j] == c){
                    visited[i][j] = 0;
                    q.add(new Node(i, j));
                }
            }
        }

        while (!q.isEmpty()){
            Node node = q.poll();
            for(int d=0;d<4;d++){
                int nx = node.x + dx[d];
                int ny = node.y + dy[d];
                if(nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
				// 4방 탐색한 경우 중 바다인 경우 -> 다리를 놓아야함
                if(map[nx][ny] == 0){
                    if(visited[nx][ny] == -1 || visited[nx][ny] > visited[node.x][node.y]+1){
                        visited[nx][ny] = visited[node.x][node.y]+1;
                        q.add(new Node(nx, ny));
                    }
                } else if(check[nx][ny] != c){ // 4방 탐색했을 때 다른 섬일 경우 -> 다리를 끝내고 다리길이 갱신
                    min_value = Math.min(min_value, visited[node.x][node.y]);
                }

            }
        }
    }

}