백준 2146 - 다리 만들기
Updated:
Java
2146 번 - 다리 만들기
문제
접근 방법
총 3가지 단계로 나누어 문제를 해결하였다.
- 각 섬을 구별하기 위해 수를 부여하여 이름을 붙혀준다.
- 지도의 모든 점을 탐색하여, 각 섬의 경계선에 있는 좌표를 저장한다.
- 각 경계선에서 출발하여, 다른 섬을 만나기 까지 탐색, 만났을 때 그 거리를 리턴한다.
섬 이름 부여 - BFS
각 섬들의 이름을 부여하기 위해, 전역 변수 인덱스를 두어 수를 부여 하였다.
0,0부터 n-1,n-1까지 모든 점을 탐색하면서, 만약 섬이 있다는 1을 만나면 그 시작 점부터 인접한 모든 점을 탐색하여 인덱스의 수로 바꾸어 준다.
위 과정을 마치면 다음과 같이 각 섬들이 구별되게 된다.
[2, 2, 2, 0, 0, 0, 0, 3, 3, 3]
[2, 2, 2, 2, 0, 0, 0, 0, 3, 3]
[2, 0, 2, 2, 0, 0, 0, 0, 3, 3]
[0, 0, 2, 2, 2, 0, 0, 0, 0, 3]
[0, 0, 0, 2, 0, 0, 0, 0, 0, 3]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 3]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 4, 4, 0, 0, 0, 0]
[0, 0, 0, 0, 4, 4, 4, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
경계선 탐색
위와 마찬가지로 0,0부터 n-1,n-1까지 모든 점을 탐색하면서 각 섬의 경계인지 확인한다.
확인하는 조건은, 현재 좌표가 섬이면서 상하좌우 인접하게 0이 있으면 섬의 경계라고 판단한다.
경계라고 확인된 좌표를 List에 저장하여, 나중에 탐색하는 위치로 저장한다.
다리 놓기 - BFS
위에서 구한 경계선에 해당하는 좌표에서 시작하여, 가장 가까운 섬을 찾는다.
이는 BFS를 통하여 구할 수 있는데, BFS를 사용하여 한 점에서 시작하여 각 좌표를 탐색하다 다른 섬을 발견하면, 그때까지 걸린 거리를 리턴하고 BFS를 종료한다.
이는 BFS는 최단거리를 찾는 알고리즘 이며, 만약 다른 섬을 찾았을 때가 제일 처음이므로 그것이 최단거리가 된다.
이렇게 모든 경계선 좌표를 확인하여, 다른 섬을 찾았을 때 거리 중 최단거리를 찾는다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int n, result = Integer.MAX_VALUE;
static int[][] map;
static int idx = 2;
static List<int[]> border;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = stoi(br.readLine());
StringTokenizer stk;
map = new int[n][n];
boolean[][] vis = new boolean[n][n];
for(int i = 0; i < n; i++) {
stk = new StringTokenizer(br.readLine());
for(int j = 0; j < n; j++) {
map[i][j] = stoi(stk.nextToken());
}
}
// 각 섬들의 이름을 지정해준다
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(map[i][j] == 1) {
MakeNameIsland(i,j);
idx++;
}
}
}
// 경계선이면 탐색 후보로 넣는다.
border = new ArrayList<>();
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(map[i][j] != 0) {
for(int k = 0; k < 4; k++) {
if(isIn(i + dy[k], j + dx[k]) && map[i + dy[k]][j + dx[k]] == 0) {
border.add(new int[] {i,j, map[i][j]});
break;
}
}
}
}
}
boolean[][] clone = new boolean[n][n];
// 경계선에서 다른 섬으로 가는 최단 거리를 구한다
for(int[] q : border) {
for(int i = 0; i < n; i++)
clone[i] = vis[i].clone();
result = Math.min(result, BFS(q[0],q[1],q[2], clone));
}
System.out.println(result);
br.close();
}
static int[] dy = {-1,1,0,0};
static int[] dx = {0,0,-1,1};
static boolean isIn(int y, int x) {
if(0 <= y && y < n && 0 <= x && x < n)
return true;
else
return false;
}
// 각 섬에게 숫자를 부여하는 메서드
private static void MakeNameIsland(int y, int x) {
Queue<int[]> queue = new LinkedList<int[]>();
queue.add(new int[] {y,x});
map[y][x] = idx;
int[] q;
int ny,nx;
while(!queue.isEmpty()) {
q = queue.poll();
y = q[0];
x = q[1];
for(int i = 0; i < 4; i++) {
ny = y + dy[i];
nx = x + dx[i];
if(isIn(ny,nx) && map[ny][nx] == 1) {
map[ny][nx] = idx;
queue.add(new int[] {ny,nx});
}
}
}
}
// 각 섬의 경계에서 다른 섬을 찾고, 그 거리를 리턴한다.
private static int BFS(int y, int x, int name, boolean[][] vis) {
Queue<int[]> queue = new LinkedList<int[]>();
queue.add(new int[] {y,x, 0});
int[] q;
int ny,nx,cnt;
while(!queue.isEmpty()) {
q = queue.poll();
y = q[0];
x = q[1];
cnt = q[2];
for(int i = 0; i < 4; i++) {
ny = y + dy[i];
nx = x + dx[i];
// 다른 섬을 찾았을 때, 그 거리를 리턴한다.
if(isIn(ny,nx) && map[ny][nx] != 0 && map[ny][nx] != name)
return cnt;
if(isIn(ny,nx) && !vis[ny][nx] && map[ny][nx] == 0) {
vis[ny][nx] = true;
queue.add(new int[] {ny,nx,cnt + 1});
}
}
}
return Integer.MAX_VALUE;
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
