[백준] 2146번: 다리 만들기 (Java)

1. 문제설명

 

 

NxN 크기의 이차원 평면상에 나라가 존재한다. 이 나라는 여러 섬으로 이루어져 있다. 육지가 없는 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다.

두 대륙을 연결하는 가장 짧은 다리 하나를 구하는 문제이다. (길이 구하기)

 

 

 

• 시간 제한: 2초
• 메모리 제한: 192MB

 

2. 접근 방식

• 섬 구분 → BFS를 사용하여 각 섬에 번호를 부여한다.
• 최소 다리 길이 계산
  • BFS를 사용하여 각 섬에서 다른 섬까지의 최단 거리를 계산한다.
  • 바다인 곳으로 확장하면서 다른 섬에 도달할 때까지의 거리를 구하고, 이 중 짧은 거리를 찾는다.

 

3. 최종 코드

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

public class Main {
    static int n; // 지도의 크기
    static int[][] map; // 지도 정보 저장
    static int[][] ground; // 육지 정보 저장
    static int[][] dis; // 거리 정보 저장
    static int minDis = Integer.MAX_VALUE; // 가장 짧은 다리 길이

    // 상하좌우
    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];
        ground = new int[n][n];
        dis = 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());
                dis[i][j] = -1; // 거리 정보를 -1로 초기화
            }
        }

        int num = 1; // 섬 번호
        // 지도를 순회하며 섬을 찾고 번호 부여
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                if(map[i][j]==1) { // 육지일 경우
                    bfs1(i, j, num++); // BFS를 통해 섬 구분
                }
            }
        }

        // 각 섬에서 다른 섬까지의 최소 다리 길이 계산
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                // 육지이고 아직 방문하지 않은 경우
                if(ground[i][j]>0 && dis[i][j]==-1) {
                    bfs2(i, j, ground[i][j]); // BFS를 통해 다리 길이 계산
                }
            }
        }

        System.out.println(minDis);
    }

    static void bfs1(int x, int y, int num) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{x, y});
        map[x][y] = 0; // 현재 위치 방문 처리
        ground[x][y] = num; // 현재 위치에 섬 번호 부여
        while(!q.isEmpty()) {
            int[] c = q.poll();
            for(int i=0; i<4; i++) { // 상하좌우 탐색
                int nx = c[0] + dx[i];
                int ny = c[1] + dy[i];
                // 지도 범위 내에 있고, 육지인 경우
                if(nx>=0 && nx<n && ny>=0 && ny<n && map[nx][ny]==1) {
                    map[nx][ny] = 0; // 방문 처리
                    ground[nx][ny] = num; // 섬 번호 부여
                    q.add(new int[]{nx, ny}); // 다음 위치 큐에 추가
                }
            }
        }
    }

    static void bfs2(int x, int y, int num) {
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{x, y});
        dis[x][y] = 0; // 시작 위치의 거리 0으로 초기화
        while(!q.isEmpty()) {
            int[] c = q.poll();
            for(int i=0; i<4; i++) { // 상하좌우 탐색
                int nx = c[0] + dx[i];
                int ny = c[1] + dy[i];
                // 다음 위치가 지도 범위 내에 있는 경우
                if(nx>=0 && nx<n && ny>=0 && ny<n) {
                    // 1. 같은 육지이면 패스
                    if(ground[nx][ny]==num) continue;
                    // 2. 바다이고, 아직 방문하지 않은 경우
                    if(ground[nx][ny]==0 && dis[nx][ny]==-1){
                        dis[nx][ny] = dis[c[0]][c[1]] + 1; // 거리 계산 & 방문 처리
                        q.add(new int[]{nx, ny}); // 다음 위치 큐에 추가
                    }
                    // 3. 바다이고, 이미 방문한 경우 (더 짧은 경로로 도달할 수 있을 경우)
                    else if(ground[nx][ny]==0 && dis[nx][ny] > dis[c[0]][c[1]]+1){
                        dis[nx][ny] = dis[c[0]][c[1]] + 1; // 거리 계산 & 방문 처리
                        q.add(new int[]{nx, ny}); // 다음 위치 큐에 추가
                    }
                    // 4. 다른 육지인 경우
                    if(ground[nx][ny]!=num && ground[nx][ny]>0) {
                        int length = dis[c[0]][c[1]]; // 현재 위치까지의 거리
                        minDis = Math.min(length, minDis); // 최소 다리 길이 계산
                    }
                }
            }
        }
    }
}

 

 

4. 다른 풀이

내 코드가 너무 복잡한가 싶어서 끝나고 다른 사람의 풀이도 찾아봤는데, 전체적인 설계는 비슷했다.

1. 섬 구분하기 / 2. 섬과 섬 사이의 최단 거리 구하기

이렇게 크게 두 가지로 구분되었다. 

2번에서 다른 풀이가 내 코드보다 조금 더 간단해서 가져와봤다.

https://velog.io/@anwlro0212/%EB%B0%B1%EC%A4%80-2146-%EB%8B%A4%EB%A6%AC-%EB%A7%8C%EB%93%A4%EA%B8%B0-JAVA

public static void bfs(int y,int x,int number) {
    Queue<Integer[]> queue=new LinkedList<>();
    visited=new boolean[map.length][map.length];
    visited[y][x] = true;
    queue.add(new Integer[] {y,x,0});

    while(!queue.isEmpty()) {
        Integer temp[] = queue.poll();
        int nowY=temp[0];
        int nowX=temp[1];
        int count=temp[2];

        //현재 위치가 바다가 아니고, 탐색을 시작한 섬의 번호와 현재 번호가 다르다면
        //최솟값 갱신
        if(map[nowY][nowX]!=0&&map[nowY][nowX]!=number) 
            min=Math.min(min,count-1);
        //count가 최소이상이면, 굳이 탐색할 필요없음. 리턴
        if(count>min)
            return;

        for(int i=0;i<4;i++) {

            int nextY=nowY+dy[i];
            int nextX=nowX+dx[i];
            if(nextY<0||nextX<0||nextY>=map.length||nextX>=map.length)
                continue;
            //다음 번호가 현재 번호와 같다면,continue
            //(우리는 섬의 테두리만을 볼 것이다 ! 섬의 중간지점을 건너뛰기 위해서는 이 작업이 필요)
            //이 작업을 함으로써 다음 지점이 바다와 연결되어 있는 테두리만을 탐색할 수 있다.
            if(map[nextY][nextX]==number)
                continue;
            if(visited[nextY][nextX]) continue;

            queue.add(new Integer[] {nextY,nextX,count+1});
            visited[nextY][nextX]=true;
        }

    }
}

 

위 풀이는 큐에 거리 정보까지 담고, visited 배열을 통해 방문 처리를 했다.

같은 섬인 경우와 방문한 경우만 continue 처리하는 것을 볼 수 있다.

나는 경우를 하나하나 다 생각하면서 작성하여 조금 복잡해졌는데, 이렇게 하면 코드가 휠씬 간단해진다.

 

5. 느낀점 or 기억할정보

문제 푸는데 조금 오래걸렸지만, 결국 풀어낼 수 있었다.

bfs2() 메서드에서 "3. 바다이고, 이미 방문한 경우"에서 if문만 사용해서 진행해봤는데, 무한루프가 돌았다.

else if로 변경하니 해결할 수 있었다.

BFS를 계속 풀다보니, 조금 발전한 것 같다는 느낌이 든다.