N x N 크기의 지도에 1(육지)과 0(바다)이 주어진다. 여러 개의 섬이 있을 때, 한 섬에서 다른 섬으로 가는 가장 짧은 다리를 건설할 때 가장 짧은 다리의 길이를 구하라.
풀이방법
BFS를 2개 사용하는 방법으로 답을 구하였다. 처음 지도를 입력받고 모든 좌표를 탐색하며 육지일 경우 음수로 지도를 고쳐주는 BFS를 1번 사용했고, 육지에서 시작하는 BFS를 구하였다.
육지에서 시작하여 다리 길이를 구하는 BFS를 구현하기 위해 count 변수를 가진 Node 클래스를 정의하였고 우선순위큐를 이용하였다. 육지 좌표 하나에서 출발하는 bfs이기 때문에 출발 위치와 가장 가까운 섬의 위치가 반대쪽에 있을 경우 일반 큐를 사용하면 count가 0인 노드가 뒤에 나오므로 이미 다른 섬과 만났을 가능성이 있기 때문에 우선순위큐를 사용했다.
인터넷을 찾아보니 모든 섬의 가장자리를 전부 큐에 넣어두고 탐색을 시작하는 방법으로 구현하는 것을 봤다. 전체적인 BFS를 1번만 돌린다는 점에서 더 효율적이라는 생각이 들었다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Node implements Comparable<Node> {
int r, c;
int count;
public Node(int r, int c) {
this.r = r;
this.c = c;
}
public Node(int r, int c, int count) {
this.r = r;
this.c = c;
this.count = count;
}
@Override
public int compareTo(Node o) {
return this.count - o.count;
}
}
public class Main {
static int N;
static int[][] map;
static int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static int answer = 10000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
map = new int[N][N];
for (int r = 0; r < N; r++) {
st = new StringTokenizer(br.readLine());
for (int c = 0; c < N; c++) {
map[r][c] = Integer.parseInt(st.nextToken());
}
}
// 섬 수 카운팅 및 지도에 섬 표시
int islandCount = 0;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (map[r][c] > 0) {
islandCount++;
islandCheck(r, c, (-1) * islandCount);
}
}
}
boolean[] islandStartCheck = new boolean[islandCount + 1];
islandStartCheck[0] = true;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (!islandStartCheck[-1 * map[r][c]]) {
islandStartCheck[-1 * map[r][c]] = true;
bfs(r, c, map[r][c]);
}
}
}
System.out.println(answer);
}
/**
* 시작 섬에서 출발하여 다른 섬 도착하는 거리 구하기
*
* @param r
* @param c
* @param startLand
*/
private static void bfs(int r, int c, int startLand) {
boolean[][] visited = new boolean[N][N];
PriorityQueue<Node> que = new PriorityQueue<>(); // 다리 길이 짧은 순으로 탐색
que.add(new Node(r, c));
visited[r][c] = true;
while (!que.isEmpty()) {
Node now = que.poll();
if (now.count > answer) { // 다리가 정답보다 길어졌다면 탐색 불필요
return;
}
for (int[] dir : dirs) {
int nextR = now.r + dir[0];
int nextC = now.c + dir[1];
if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= N || visited[nextR][nextC]) continue;
if (map[nextR][nextC] == startLand) { // 같은 섬
visited[nextR][nextC] = true;
que.add(new Node(nextR, nextC, 0));
} else if (map[nextR][nextC] < 0) { // 다른 섬
answer = Math.min(answer, now.count);
return;
} else { // 바다
visited[nextR][nextC] = true;
que.add(new Node(nextR, nextC, now.count + 1));
}
}
}
}
/**
* 같은 섬끼리 같은 번호로 지도 초기화 해주기. BFS
*
* @param r
* @param c
* @param islandNum
*/
private static void islandCheck(int r, int c, int islandNum) {
Deque<Node> que = new ArrayDeque<>();
que.add(new Node(r, c));
map[r][c] = islandNum;
while (!que.isEmpty()) {
Node now = que.poll();
for (int[] dir : dirs) {
int nextR = now.r + dir[0];
int nextC = now.c + dir[1];
if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= N) continue;
if (map[nextR][nextC] > 0) {
map[nextR][nextC] = islandNum;
que.add(new Node(nextR, nextC));
}
}
}
}
}
