알고리즘 풀이 - 백준 2146(다리 만들기, 그래프(BFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

섬과 섬을 가장 짧은 다리로 잇는 경우 다리의 길이를 구하는 문제

 

 

2. 풀이

 

이 문제는 그래프 탐색 중 난이도가 좀 있는 문제이다. 일반적으로 가장 간단히 생각해볼 수 있는 해결책은 다음과 같다.

⑴ 각각의 섬을 다른 번호로 저장한다.
⑵ 각 섬의 모든 위치에서 BFS 탐색을 시작하여 다른 번호의 섬에 가장 먼저 도달하는 경우를 정답으로 한다.

그런데 위의 방법으로 하면 문제를 풀 수 없다.

왜냐하면, 지도의 크기가 최대 100이라고 할 때, 100x100=10,000의 크기의 지도가 될 수 있는데, 이 때 섬의 개수는 최대 5000개가 될 수 있다.(아래와 같이)

1010101...
0101010...
...

위 형태와 같이 가능하므로 10,000/2 = 5,000개가 될 수 있는데 모든 위치에서 BFS탐색을 시작한다고 하면 전체 시간복잡도는 아래와 같이 된다.

시간복잡도 : O(NN x NN / 2) - 모든 위치에서 탐색 시작 x BFS의 시간복잡도

 

 

따라서,  시간 내에 풀 수 없거나 효율적으로 해결할 수 없다.

 

따라서, 이 문제의 경우는 다음과 같이 풀 수 있다.

⑴ 각각의 섬을 다른 번호로 저장한다.
⑵ 각 섬의 모든 위치의 주변 바다를 현재 섬의 번호로 변경시킨다.
⑶ 주변 정점이 바다가 아닌 다른 섬의 번호가 되는 최초의 경우를 찾으면 추가 탐색을 종료하고 그 거리를 구한다.

 

그림으로 이해해보자.

 

위와 같은 순서로, 각 떨어진 섬을 다른 번호로 매기고 주변 바다를 해당 섬의 번호로 지정한 다음 서로 만나는 부분의 거리를 구하면 된다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

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

public class Main{
    static int n;
    static int[][] graph;
    static int[][] island;
    static int[][] distance;
    static boolean[][] visited;

    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0 ,1};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // ****************** 그래프 초기화 ********************
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = null;
        graph = new int[n][n];
        Queue<Map> s = new LinkedList<>();
        for(int i=0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j < n; j++){
                graph[i][j] = Integer.parseInt(st.nextToken());
                
                // 섬 부분을 모두 Queue에 추가해둔다.
                if(graph[i][j] == 1) s.offer(new Map(i, j));
            }
        }
        // ***************** 그래프 초기화 완료 *****************


        // ***************** 섬 마다 구분하기 위해 다른 번호로 저장 ***************
        island = new int[n][n];
        distance = new int[n][n];
        visited = new boolean[n][n];
        int cnt = 1;
        Queue<Map> q = new LinkedList<>();
        
        for(int i=0; i < n; i++){
            for(int j=0; j < n; j++){
                if(visited[i][j] || graph[i][j] == 0) continue;
                q.offer(new Map(i, j));
                visited[i][j] = true;

                // 연결된 섬의 정보를 모두 체크(각 섬을 다른 번호로 저장)
                while(!q.isEmpty()){
                    Map u = q.poll();
                    island[u.y][u.x] = cnt;

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

                        if(0 <= ny && ny < n && 0 <= nx && nx < n && !visited[ny][nx] && graph[ny][nx] == 1){
                            visited[ny][nx] = true;
                            q.offer(new Map(ny, nx));
                        }
                    }
                }
                cnt++;
            }
        }
        // *********************** 섬 구분 코드 완료 *****************************


        // ******************* 현재 섬 주변의 모든 바다를 동일 섬 번호로 메꿈 *************
        while(!s.isEmpty()){
            Map u = s.poll();
            for(int i=0; i < 4; i++){
                int ny = u.y + dy[i];
                int nx = u.x + dx[i];

                // 위치에 있고 방문되지 않았다면 섬이 아니라 바다이므로 작업 수행
                if(0 <= ny && ny < n && 0 <= nx && nx < n && !visited[ny][nx]){
                    visited[ny][nx] = true;
                    s.offer(new Map(ny, nx));
                    
                    // 섬으로 부터의 거리를 저장(이전의 +1)
                    distance[ny][nx] = distance[u.y][u.x] + 1;
                    
                    // 섬 값으로 동일하게 지정
                    island[ny][nx] = island[u.y][u.x];
                }
            }
        }
        // ******************* 바다를 섬으로 메꾸는 코드 완료 ***************************
        
        
        
        // ****************** 인접한 정점 중 번호가 다른 것의 거리 계산 *****************
        int ans = -1;
        for(int i=0; i < n; i++){
            for(int j=0; j < n; j++){
                for(int k=0; k < 4; k++){
                    int ni = i + dy[k];
                    int nj = j + dx[k];
                    if(0 <= ni && ni < n && 0 <= nj && nj < n && island[i][j] != island[ni][nj]){
                    
                        // 인접 정점의 번호가 다르면, 그 거리를 더하면 다리의 길이가 됨(섬 간 연결)
                        if(ans == -1 || ans > distance[i][j] + distance[ni][nj]){
                            ans = distance[i][j] + distance[ni][nj];
                        }
                    }
                }
            }
        }
        // ******************** 인접 정점 계산 완료 *******************************
        
        System.out.println(ans);
        br.close();
    }
}

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

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.