BOJ 2146
위 문제는 백준 사이트의 알고리즘 2146 문제에 관한 설명입니다.
BOJ 2146
다리만들기
여러 섬으로 이루어진 나라가 있다.
이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다.
하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다.
그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.
이 나라는 N×N크기의 이차원 평면상에 존재한다.
이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다.
다음은 세 개의 섬으로 이루어진 나라의 지도이다.
위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다.
이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다.
가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다.
다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.
물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나,
위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다)
지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.
입력
첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다.
그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다.
항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.
출력
첫째 줄에 가장 짧은 다리의 길이를 출력한다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
static int dx[] = { -1, 0, 1, 0 };
static int dy[] = { 0, 1, 0, -1 };
static int visit[][];
static int map[][];
static Queue<Island> queue;
static int result;
static int N;
static int MIN;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
N = scanner.nextInt();
map = new int[N][N];
visit = new int[N][N];
queue = new LinkedList<Island>();
MIN = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int land = scanner.nextInt();
if (land == 1) {
queue.add(new Island(i, j, 0));
}
map[i][j] = -land;
}
}
int color = 1;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == -1) {
div(i, j, color);
color++;
}
}
}
BFS();
System.out.println(MIN);
scanner.close();
}
static void BFS() {
while (!queue.isEmpty()) {
Island temp = queue.poll();
int currentX = temp.x;
int currentY = temp.y;
int count = temp.count;
for (int i = 0; i < 4; i++) {
int nextX = currentX + dx[i];
int nextY = currentY + dy[i];
if (nextX < 0 || nextY < 0 || N <= nextX || N <= nextY) {
continue;
}
if (map[nextX][nextY] == 0) {
queue.add(new Island(nextX, nextY, count + 1));
map[nextX][nextY] = map[currentX][currentY];
visit[nextX][nextY] = count + 1;
} else if (map[currentX][currentY] != map[nextX][nextY]) {
result = visit[nextX][nextY] + visit[currentX][currentY];
if (result < MIN) {
MIN = result;
}
}
}
}
}
static void div(int x, int y, int color) {
map[x][y] = color;
for (int i = 0; i < 4; i++) {
int nextX = x + dx[i];
int nextY = y + dy[i];
if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < N) {
if (map[nextX][nextY] == -1) {
map[nextX][nextY] = color;
div(nextX, nextY, color);
}
}
}
}
}
class Island {
public int x;
public int y;
public int count;
public Island(int x, int y, int count) {
this.x = x;
this.y = y;
this.count = count;
}
}
이번 문제는 DFS(섬을 구분할 때)와 BFS(바다를 건널 때? 다리를 만들 때)를 이용해서 풀었습니다.
이번 문제의 해결법은?
1. 다른 섬들과의 구분을 만들어 주고싶었습니다.
같은 1로 섬들을 다 고려한다면 섬에서 나와서 바다를 BFS로 search하다가
그 섬의 가장 가까운 곳도 1이니 같은 섬인지 다른 섬인지 구분이 힘듭니다.
div를 활용해서 다른 섬들과의 count를 주고자 처음에 1로 받은 땅들은 다 -land로 바꾼 후 각 섬마다 번호를 다르게 지정해 주었습니다.
첫번째 섬, 두번째 섬.. 쭉~
2. BFS는 땅에서 바다를 건너가거나 할 때 Island 클래스에 count값을 하나씩 늘려주면서 다음 칸을 둘러봅니다.
그리고 다음 칸의 값들과 다른 값이 있다? 0이라면 visit의 카운트를 늘려주고, 다른 숫자라면 그곳은 다른섬에 만났다는 것입니다.
그렇다면 지나온 값의 결과와 여태까지 가장 작게 저장했던 결과 값을 비교합시다.
더 작은 결과를 바라니 작은 값을 MIN 값에 저장합시다.