문제
17472번: 다리 만들기 2 (acmicpc.net)
해결방법
-
섬의 개수와 위치 체크
BFS를 통해 이어지는 곳들을 모두 같은 섬으로 표시하고 BFS를 한 횟수만큼 섬이 있다고 보면 된다. -
다리 찾기
N, M의 크기 제한이 크지 않기 때문에 2차원 배열을 완전 탐색하며 해당 위치가 섬일 경우 4방향으로 다리를 놓을 수 있는지 다 찾아보면 된다. 그리고 다리를 놓을 수 있다면 시작 섬과 도착 섬의 거리의 최솟값을 갱신해준다. -
Union, Find를 통한 크루스칼 알고리즘
각 섬끼리의 거리의 최솟값을 통해 간선들을 중복되지 않게 만들고 해당 간선들을 우선순위 큐를 이용해 거리가 짧은 간선부터 순새대로 union find를 수행하여 섬들을 묶어준다. 마지막에 모든 섬이 union 되었는지 확인한다.
동작과정
-
2차원 boolean 배열 맵에 입력을 받는다 0 : false 1: true
-
2차원 int 배열에 BFS를 통해 섬들의 번호를 넣는다.
-
2차원
islands배열을 모두 탐색하며 각 섬끼리 다리를 놓을 수 있는거리를 다 구하고 최솟값을 비교하여min_distance에 저장한다. -
min_distance를 통해 중복 없이 각 섬끼리 거리가 가장 짧은 다리를 모두 선택해서 우선순위 큐에 넣는다. -
거리가 짧은 다리부터 순서대로
union,find를 수행한다. -
모든 간선에 대해 반복문을 마치고 모든 섬들이 이어졌는지 확인하고 답을 출력한다.
코드
import java.io.*;
import java.util.*;
/*
* 1. BFS 를 통해 배열을 탐색하여 섬들을 표시한다.
* 2. DFS 를 통해 배열을 탐색하여 섬들 끼리의 최소 거리를 구한다. (단 길이가 1인 경우 제외함)
* 3. Union find 을 통한 크루스칼 알고리즘을 사용하여 최종 값을 구한다.
* 4. 이 때 모든 섬이 union 되지 않았으면 -1을 출력해야 한다.
*/
public class Main {
// 2차원 배열의 위치를 나타냄
private static class Point{
int y;
int x;
public Point(int y, int x) {
this.y = y;
this.x = x;
}
}
// 각 다리를 나타냄
private static class Bridge{
int a;
int b;
int length;
public Bridge(int a, int b, int length) {
this.a = a;
this.b = b;
this.length = length;
}
}
private final static int[][] D = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private static int N, M;
private static int[] parent;
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(in.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// map 에 받아온 정보를 나타낸다 0 : false 1 : true
// islands 에 각 섬의 정보를 번호로 나타낸다.
boolean[][] map = new boolean[N][M];
int[][] islands = new int[N][M];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(in.readLine());
for(int j = 0; j < M; j++) {
if(st.nextToken().equals("1"))
map[i][j] = true;
}
}
// map 에 저장된 정보를 토대로 BFS 를 수행하여 islands 에 각 섬의 번호를 표시한다.
int group = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(islands[i][j] == 0 && map[i][j])
BFS(map, islands, new Point(i, j), ++group);
}
}
// 각 섬끼리의 다리의 최소 거리를 나타내기 위한 배열 초기에 Integer.MAX_VALUE 를 채워놓는다.
int[][] min_distance = new int[group+1][group+1];
for(int i = 1; i <= group; i++) {
Arrays.fill(min_distance[i], Integer.MAX_VALUE);
}
// 2차원 배열을 완전 탐색하여 존재 할 수 있는 모든 다리의 길이의 경우의 수를 구한다. 그리고 그 중 가장 작은 값들을 저장한다. ( 단 1이상)
for(int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
// 섬이 있는 곳이면 4방향으로 다리를 놓을 수 있는지 탐색한다.
if (islands[i][j] != 0) {
for(int d = 0; d < 4; d++) {
int y = i + D[d][0];
int x = j + D[d][1];
int length = 0;
// 다른 섬에 도달하거나 배열 밖으로 나갈 때 까지 반복문을 수행하며 길이를 잰다.
while(isInBound(y, x) && islands[y][x] == 0) {
length++;
y += D[d][0];
x += D[d][1];
}
// 범위를 벗어낫거나 길이가 1보다 작거나 같으면 다리를 놓을 수 없음
if(!isInBound(y, x) || length <= 1)
continue;
// 시작 점의 섬의 번호와 마지막 점의 섬의 번호가 다르면 다리를 놓을 수 있다.
// 이 때의 거리를 구해서 이전에 저장된 거리보다 가까우면 현재의 거리를 저장한다.
if(islands[y][x] != islands[i][j]) {
int from = islands[i][j];
int to = islands[y][x];
min_distance[from][to] = Math.min(min_distance[from][to], length);
min_distance[to][from] = Math.min(min_distance[from][to], length);
}
}
}
}
}
// union find 를 위한 parent 배열을 선언하고 초기화 해준다.
parent = new int[group+1];
for(int i = 0; i <= group; i++)
parent[i] = i;
// 모든 간선들을 저장할 우선순위 큐
PriorityQueue<Bridge> bridges = new PriorityQueue<>((o1, o2) -> o1.length - o2.length);
// 중복된 간선을 저장하지 않기 위해 j = i+1 부터 탐색하여 다리를 놓을 수 있는 (Integer.MAX_VALUE) 가 아닌 모든 간선들을 우선순위 큐에 저장한다.
for(int i = 1; i <= group; i++) {
for(int j = i+1; j <= group; j++) {
if(min_distance[i][j] != Integer.MAX_VALUE)
bridges.add(new Bridge(i, j, min_distance[i][j]));
}
}
// 간선들의 가중치를 더할 sum
int sum = 0;
// 모든 간선들을 가중치가 낮은 순서대로 보며 간선의 양 섬이 union 이 되지 않았다면 둘을 union 하고 가중치를 sum 에 더한다.
while(!bridges.isEmpty()) {
Bridge bridge = bridges.poll();
int a = bridge.a;
int b = bridge.b;
if(find(a) != find(b)) {
union(a, b);
sum += bridge.length;
}
}
// 모든 섬이 union 이 되었는지 확인한다.
int p = find(1);
boolean find = true;
for(int i = 2; i <= group; i++) {
if(find(i) != p)
find = false;
}
// 모든 섬이 연결 됨
if(find)
out.write(sum + "");
// 모든 섬이 연결되지 않음
else
out.write("-1");
out.flush();
}
// 2차원 배열을 BFS 로 순회하며 group 에 해당하는 섬을 모두 islands 에 표시해주기 위한 함수
private static void BFS(boolean[][] map, int[][] islands, Point start, int group) {
// 시작 지점을 설정
Queue<Point> q = new ArrayDeque<>();
q.offer(start);
islands[start.y][start.x] = group;
// 4방향 탐색하며 해당 위치가 map 에서 섬으로 표시 (true) 되어 있고, 아직 islands 에서 선택되지 않은 곳이면 그곳을 해당 group 의 섬으로 표시하고 큐에 추가한다.
while(!q.isEmpty()) {
Point now = q.poll();
for(int d = 0; d < 4; d++) {
int dy = now.y + D[d][0];
int dx = now.x + D[d][1];
if(isInBound(dy, dx) && map[dy][dx] && islands[dy][dx] == 0) {
islands[dy][dx] = group;
q.offer(new Point(dy, dx));
}
}
}
}
// 각 섬을 union
private static void union(int a, int b) {
a = find(a);
b = find(b);
if(a < b)
parent[b] = a;
else
parent[a] = b;
}
// 각 섬의 집합의 대표를 찾음
private static int find(int a) {
if(parent[a] == a)
return a;
else
return find(parent[a]);
}
// 배열 경계 확인
private static boolean isInBound(int y, int x) {
return y >= 0 && y < N && x >= 0 && x < M;
}
}
성장 중