[Algorithm] 2146 - 다리만들기 문제 풀이

목차

---

1. 문제 설명

2. 정답

 

 

 

 

 

1. 문제 설명

---

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

 

지도가 주어질 때 가장 짧은 다리를 하나 놓아 두 대륙을 연결하는 방법을 찾는 문제다.

 

문제 예시 지도

 

• 바다 = 0
• 육지 = 1

위의 그림과 같이 지도가 주어지면 회색 영역의 섬을 dfs로 구한다.

바다와 육지가 각각 0, 1의 값을 사용하기 때문에 각각의 섬에 2부터 번호를 부여한다.

 

즉 dfs로 모든 영역을 순회했을 때 각각의 섬은 오른쪽 사진과 같은 번호를 부여받는다.

 

 

두 대륙을 연결하는 가장 짧은 다리는 (해안선과 근접한 육지) - (해안선과 근접한 육지)간의 최단 거리와 같다.

 

Q. 최단 거리를 구해야한다면?

A. bfs를 써야 한다는 뜻이다!

 

 

 

그렇다 이 문제는 dfs + bfs 짬뽕인 것이다...!!!!

맨날 dfs, bfs 각각 단일 알고리즘을 적용한 문제만 풀다가

둘을 섞은 문제는 처음이라 섬간의 최단 거리 구하는 부분 구할 때 헤맸다 ㅠㅠ

 

 

 

dfs로 모든 영역을 순회할 때 해안선에 근접한 육지의 좌표를 기록해둔다.

---

💡 해안선에 근접한 육지 좌표 구하는 방법

 

dfs로 모든 영역을 순회할 때 해안선인지 체크하는 지역변수를 생성한다. (ex. isCoast)

현재 위치를 기준으로 상하좌우를 탐색했을 때 좌표에 부여된 값이 하나라도 0이면 인접한 곳에 바다가 있다는 뜻으로 

현재 위치가 해안선에 근접한 육지라는 의미가 된다.

 

현재 위치가 해안선에 근접한 육지라면 준비한 리스트에 해당 좌표를 기록한다.

---

 

 

그리고 각 좌표에 부여된 값(바다 = 0, 섬 = 2, 3, 4 ..)이 0이 아니면 bfs로 모든 영역을 순회하여 시작점과 다른 섬 번호를 갖고 있다면 시작점과의 거리가 최솟값인지 비교하는 알고리즘이 필요하다.

 

 

 

 

 

2. 정답

---

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

public class Main {
    public static int[] dX = {0, 0, -1, 1};
    public static int[] dY = {1, -1, 0, 0};
    public static int N;
    public static int[][] map;
    public static boolean[][] visited;
    public static List<List<int[]>> islands = new ArrayList<>();
    public static int min = Integer.MAX_VALUE;

    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];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(input[j]); // 0 = 바다, 1 = 육지
            }
        }

        // 1. 섬 분류 후 해안가 정보 저장
        int count = 2;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j] && map[i][j] == 1) {
                    List<int[]> coastlines = new ArrayList<>();
                    dfs(i, j, count, coastlines);
                    islands.add(coastlines);
                    count++;
                }
            }
        }

        // 2. 각 섬마다 BFS 실행해서 최단 다리 찾기
        for(int i = 0; i < islands.size(); i++) {
            for(int[] pos : islands.get(i)) {
                bfs(pos[0], pos[1], map[pos[0]][pos[1]]);
            }
        }

        System.out.print(min);
    }

    public static void dfs(int x, int y, int count, List<int[]> coastlines) {
        visited[x][y] = true;
        map[x][y] = count;
        boolean isCoast = false;

        for (int i = 0; i < 4; i++) {
            int newdX = x + dX[i];
            int newdY = y + dY[i];

            if (newdX < 0 || newdX >= N || newdY < 0 || newdY >= N) continue;

            if (map[newdX][newdY] == 0) isCoast = true;

            if (!visited[newdX][newdY] && map[newdX][newdY] == 1) {
                dfs(newdX, newdY, count, coastlines);
            }
        }

        if (isCoast) {
            coastlines.add(new int[]{x, y});
        }
    }


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

        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            int nowX = now[0];
            int nowY  = now[1];
            int distance = now[2];

            // 현재가 해안가가 아니고 다른 섬을 만났을 때
            if(map[nowX][nowY] != 0 && map[nowX][nowY] != islandId) {
                min = Math.min(min, distance - 1);
                return;
            }

            if(distance > min) return;

            for (int i = 0; i < 4; i++) {
                int newdX = now[0] + dX[i];
                int newdY = now[1] + dY[i];

                if(newdX < 0 || newdX >= N || newdY < 0 || newdY >= N) continue;
                // 같은 섬이 아니면 방문
                if (!visited[newdX][newdY] && map[newdX][newdY] != islandId) {
                    visited[newdX][newdY] = true;
                    queue.add(new int[]{ newdX, newdY, distance + 1 });
                }
            }
        }
    }
}