[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 });
}
}
}
}
}