문제
섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.
섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.
다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.
다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.
섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다.
아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.
| 다리의 총 길이: 13 D는 2와 4를 연결하는 다리이고, 3과는 연결되어 있지 않다. | 다리의 총 길이: 9 (최소) |
다음은 올바르지 않은 3가지 방법이다
| C의 방향이 중간에 바뀌었다 | D의 길이가 1이다. | 가로 다리인 A가 1과 가로로 연결되어 있지 않다. |
다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다.
| A의 길이는 4이고, B의 길이도 4이다. 총 다리의 총 길이: 4 + 4 + 2 = 10 | 다리 A: 2와 3을 연결 (길이 2) 다리 B: 3과 4를 연결 (길이 3) 다리 C: 2와 5를 연결 (길이 5) 다리 D: 1과 2를 연결 (길이 2) 총 길이: 12 |
나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.
출력
모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.
제한
- 1 ≤ N, M ≤ 10
- 3 ≤ N×M ≤ 100
- 2 ≤ 섬의 개수 ≤ 6
예제 입력 1
7 8
0 0 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
1 1 0 0 0 1 1 0
0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1예제 출력 1
9예제 입력 2
7 8
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
1 1 0 0 0 0 1 1
1 1 0 0 0 0 1 1
1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1예제 출력 2
10예제 입력 3
7 8
1 0 0 1 1 1 0 0
0 0 1 0 0 0 1 1
0 0 1 0 0 0 1 1
0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0
0 1 1 1 0 0 0 0
1 1 1 1 1 1 0 0예제 출력 3
9예제 입력 4
7 7
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1
0 0 0 0 0 0 0
1 1 1 0 1 1 1
1 1 1 0 1 1 1
1 1 1 0 1 1 1예제 출력 4
-1풀이
이 문제는 bfs(너비 우선 탐색), dfs(깊이 우선 탐색), kruskal(크루스칼) 알고리즘을 이용해서 풀 수 있었다. 3단계로 나눠서 풀 수 있는데 첫 번째로 DFS를 이용해서 각 섬에 번호를 매기고 두 번째로는 BFS를 이용해서 거리를 계산한 뒤에 마지막으로 크루스칼을 이용해서 답을 구했다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
public class Main {
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
static int N; //최대 행
static int M; //최대 열
static int[] parent; //크루스칼 알고리즘을 위한 부모 배열
static int[][] map; //전체 좌표 배열
static boolean[][] visited; //라벨링에 사용할 방문 배열
static Queue<Pair> queue = new LinkedList<>(); //섬에 포함되는 모든 좌표를 위한 큐
static PriorityQueue<Pair> pq = new PriorityQueue<>(); //크루스칼 알고리즘에 사용할 우선순위 큐
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
M = Integer.parseInt(input[1]);
map = new int[N][M];
visited = new boolean[N][M];
for(int i=0; i<N; i++) {
input = br.readLine().split(" ");
for(int j=0; j<M; j++) {
map[i][j] = Integer.parseInt(input[j]);
}
}
int island = 0;
for(int i=0; i<N; i++) { //라벨링
for(int j=0; j<M; j++) {
if(map[i][j]==1 && !visited[i][j]) {
visited[i][j] = true;
map[i][j] = island+1;
dfs(i, j, island+1);
island++;
queue.add(new Pair(i, j, map[i][j], -1, 0));
}
}
}
while(!queue.isEmpty()) { //각 섬간의 거리 계산
bfs(queue.poll(), island);
}
parent = new int[island+1];
for(int i=1; i<=island; i++)
parent[i] = i;
int ans = 0;
int cnt = 0; //모든 섬 연결 가능한지 체크하기 위한 변수
while(!pq.isEmpty()) { //크루스칼 알고리즘 진행
Pair temp = pq.poll();
int x = temp.x;
int y = temp.y;
if(find(x)==find(y)) continue;
union(x, y);
cnt++;
ans += temp.cnt;
}
if(cnt==island-1)
System.out.println(ans);
else
System.out.println(-1);
}
public static void bfs(Pair start, int island) { //각 섬간의 거리를 측정
Queue<Pair> queue = new LinkedList<>();
boolean[][] v = new boolean[N][M]; //좌표 방문 체크 배열
boolean[] v2 = new boolean[island+1]; //섬 방문 체크 배열
queue.add(new Pair(start.x, start.y, start.label, -1, 0));
v[start.x][start.y] = true;
while(!queue.isEmpty()) {
Pair temp = queue.poll();
if(temp.idx==-1) { //방향 설정이 안된 초기 좌표
for(int i=0; i<4; i++) {
int nx = temp.x+dx[i];
int ny = temp.y+dy[i];
if(nx<0 || nx>=N || ny<0 || ny>=M || v[nx][ny]) continue;
v[nx][ny] = true;
if(map[nx][ny]==0) {
queue.add(new Pair(nx, ny, temp.label, i, temp.cnt+1));
}
else {
if(map[nx][ny]!=temp.label && !v2[map[nx][ny]] && temp.cnt>=2) {
v2[map[nx][ny]] = true;
pq.add(new Pair(temp.label, map[nx][ny], 0, 0, temp.cnt));
}
}
}
}
else { //방향이 정해진 좌표
int nx = temp.x+dx[temp.idx];
int ny = temp.y+dy[temp.idx];
if(nx<0 || nx>=N || ny<0 || ny>=M || v[nx][ny]) continue;
v[nx][ny] = true;
if(map[nx][ny]==0) { //바다면 계속 진행
queue.add(new Pair(nx, ny, temp.label, temp.idx, temp.cnt+1));
}
else {
if(map[nx][ny]!=temp.label && !v2[map[nx][ny]] && temp.cnt>=2) { //바다가 아닌 경우 출발 섬과 번호가 다르고 방문하지 않은 섬이고 거리가 2인 경우
v2[map[nx][ny]] = true;
pq.add(new Pair(temp.label, map[nx][ny], 0, 0, temp.cnt));
}
}
}
}
}
public static void dfs(int x, int y, int label) { //섬 라벨링
for(int i=0; i<4; i++) {
int nx = x+dx[i];
int ny = y+dy[i];
if(nx<0 || nx>=N || ny<0 || ny>=M || visited[nx][ny] || map[nx][ny]!=1) continue;
visited[nx][ny] = true;
map[nx][ny] = label;
queue.add(new Pair(nx, ny, label, -1, 0)); //섬인 경우 거리 측정을 위해 모두 큐에 넣음
dfs(nx, ny, label);
}
}
public static void union(int a, int b) {
a = find(a);
b = find(b);
if(a<b)
parent[b] = a;
else
parent[a] = b;
}
public static int find(int a) {
if(parent[a]==a)
return a;
return parent[a] = find(parent[a]);
}
public static class Pair implements Comparable<Pair>{
int x; //행
int y; //열
int label; //섬 번호
int idx; //진행 방향
int cnt; //거리
public Pair(int x, int y, int label, int idx, int cnt) {
this.x = x;
this.y = y;
this.label = label;
this.idx = idx;
this.cnt = cnt;
}
public int compareTo(Pair p) {
return this.cnt > p.cnt ? 1 : -1;
}
}
}