# BOJ02146 다리 만들기
https://www.acmicpc.net/problem/2146 (opens new window)
여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.
이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다.
1은 육지를 나타내고, 0은 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다.
# Location
좌표를 관리하기 위한 Location이다.
private static class Location {
private int x;
private int y;
public Location(int x, int y) {
this.x = x;
this.y = y;
}
}
# 섬 번호 지정
육지는 모두 1로 표기 되어 있기 때문에 섬을 나누기 위한 numbering을 진행한다.
// 섬에 번호 지정
private static void numberingIsland() {
boolean[][] visited = new boolean[n][n]; // 번호 지정을 위한 방문 처리 배열
int count = 1;
// 방문하지 않는 섬을 탐색하며 numbering
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j] == 1 && !visited[i][j]) {
Queue<Location> queue = new LinkedList<>();
queue.add(new Location(i, j));
graph[i][j] = count;
visited[i][j] = true;
while (!queue.isEmpty()) {
Location location = queue.poll();
for (int d = 0; d < 4; d++) {
int x = location.x + dx[d];
int y = location.y + dy[d];
if (x >= 0 && x < n && y >= 0 && y < n && !visited[x][y] && graph[x][y] == 1) {
queue.add(new Location(x, y));
graph[x][y] = count;
visited[x][y] = true;
}
}
}
count++;
}
}
}
}
넘버링을 완료하면 각 섬 별로 특정한 번호가 부여된다. 주의해야 할 점은 지역 변수로 visited을 따로 작성하여 넘버링을 위한 변수를 사용하였다. 전역 변수로 선언한 visited와 다른 용도로 사용하기 위해 분리하였다.
1 1 1 0 0 0 0 2 2 2
1 1 1 1 0 0 0 0 2 2
1 0 1 1 0 0 0 0 2 2
0 0 1 1 1 0 0 0 0 2
0 0 0 1 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0
0 0 0 0 3 3 0 0 0 0
0 0 0 0 3 3 3 0 0 0
0 0 0 0 0 0 0 0 0 0
# bfs
이제 섬에 대한 위치는 모두 파악되었다.
모든 섬을 방문하며 다른 섬에 방문할 때 섬 사이의 거리를 구할수 있도록 너비 우선 탐색을 진행한다.
// 섬 주위를 탐색하며 다른 섬에 닿을 때 까지 너비 우선 탐색 진행
private static void bfs(int x, int y) {
visited = new boolean[n][n]; // 다리 길이 중간 저장을 위해 방문 기록 초기화
Queue<Location> queue = new LinkedList<>();
queue.add(new Location(x, y));
visited[x][y] = true;
int number = graph[x][y]; // 다른 섬인지 판별하기 위한 섬 번호
while (!queue.isEmpty()) {
Location location = queue.poll();
for (int i = 0; i < 4; i++) {
x = location.x + dx[i];
y = location.y + dy[i];
if (isLocation(x, y)) {
// 다른 섬이면 다리 길이 최솟값 갱신
if (graph[x][y] != 0 && graph[x][y] != number) {
min = Math.min(min, distances[location.x][location.y]);
} else if (graph[x][y] == 0) { // 바다이면 다리 길이 추가 및 방문처리
queue.add(new Location(x, y));
distances[x][y] = distances[location.x][location.y] + 1;
visited[x][y] = true;
}
}
}
}
}
private static boolean isLocation(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y]) {
return false;
}
return true;
}
# 제출 코드
아래는 최종 제출 코드이다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class BOJ2146 {
private static int n;
private static int min = Integer.MAX_VALUE;
private static int[][] graph;
private static int[][] distances;
private static boolean[][] visited;
private static final int[] dx = {-1, 0, 1, 0};
private static final int[] dy = {0, 1, 0, -1};
private static class Location {
private int x;
private int y;
public Location(int x, int y) {
this.x = x;
this.y = y;
}
}
// 섬 주위를 탐색하며 다른 섬에 닿을 때 까지 너비 우선 탐색 진행
private static void bfs(int x, int y) {
visited = new boolean[n][n]; // 다리 길이 중간 저장을 위해 방문 기록 초기화
Queue<Location> queue = new LinkedList<>();
queue.add(new Location(x, y));
visited[x][y] = true;
int number = graph[x][y]; // 다른 섬인지 판별하기 위한 섬 번호
while (!queue.isEmpty()) {
Location location = queue.poll();
for (int i = 0; i < 4; i++) {
x = location.x + dx[i];
y = location.y + dy[i];
if (isLocation(x, y)) {
// 다른 섬이면 다리 길이 최솟값 갱신
if (graph[x][y] != 0 && graph[x][y] != number) {
min = Math.min(min, distances[location.x][location.y]);
// 바다이면 다리 길이 추가 및 방문처리
} else if (graph[x][y] == 0) {
queue.add(new Location(x, y));
distances[x][y] = distances[location.x][location.y] + 1;
visited[x][y] = true;
}
}
}
}
}
private static boolean isLocation(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y]) {
return false;
}
return true;
}
// 섬에 번호 지정
private static void numberingIsland() {
boolean[][] visited = new boolean[n][n]; // 번호 지정을 위한 방문 처리 배열
int count = 1;
// 방문하지 않는 섬을 탐색하며 numbering
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j] == 1 && !visited[i][j]) {
Queue<Location> queue = new LinkedList<>();
queue.add(new Location(i, j));
graph[i][j] = count;
visited[i][j] = true;
while (!queue.isEmpty()) {
Location location = queue.poll();
for (int d = 0; d < 4; d++) {
int x = location.x + dx[d];
int y = location.y + dy[d];
if (x >= 0 && x < n && y >= 0 && y < n && !visited[x][y] && graph[x][y] == 1) {
queue.add(new Location(x, y));
graph[x][y] = count;
visited[x][y] = true;
}
}
}
count++;
}
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
graph = new int[n][n];
distances = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = scanner.nextInt();
// 다리 길이 누적을 위한 distances. 섬이 위치한 곳은 1로 표기
if (graph[i][j] == 1) {
distances[i][j] = 1;
}
}
}
numberingIsland(); // 섬에 번호 지정
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j] != 0) { // 섬인 곳 방문
bfs(i, j);
}
}
}
// 최초 섬인 곳을 1로 표기 했기 때문에 -1
System.out.println(min - 1);
}
}