[백준] 17472 다리 만들기 2 - 시뮬레이션 + 구현 + BFS(너비우선탐색) + 최소스패닝트리(MST, Minimum Spanning Tree) + 크루스칼(Kruskal) + 유니온파인드(Union Find) JAVA

https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

 

코드설명

시뮬레이션 + 구현 + BFS(너비우선탐색) + 최소스패닝트리(MST, Minimum Spanning Tree) + 크루스칼(Kruska) 문제입니다. 

 

문제의 구현과정을 정리해보았습니다.

 

1. 섬 인덱싱: 입력된 지도에서 1로 표시된 섬들을 찾아 각각을 다른 숫자로 인덱싱합니다. 이때 groupingMapBFS 메서드를 사용하여 BFS로 각 섬을 그룹화하고 인덱스를 부여합니다.
2. 최단 거리 계산: 각 섬을 인덱싱한 후, distanceBetweenIsland 배열에는 섬 사이의 최단 다리 길이를 계산하여 저장합니다. 이를 위해 findNextIsland 메서드에서 BFS로 섬 간의 거리를 찾아 모두 PriorityQueue에 넣습니다.
3. 크루스칼 알고리즘: 각 섬 간의 최단 거리를 기반으로 크루스칼 알고리즘을 사용하여 최소 비용으로 모든 섬을 연결합니다. 이때, kruskal 메서드에서는 최소 힙(PriorityQueue)을 사용하여 간선을 처리하고, 각 섬이 동일한 그룹에 속해 있는지 확인하여 싸이클을 방지합니다.
4. 출력: 최종적으로 모든 섬을 연결하는 최소 비용을 출력합니다. 만약 모든 섬이 연결되지 않는다면 -1을 출력합니다.

 

 

문제에서 가장 헷갈리는 부분은 MST, 최소스패닝 트리를 적용하는것입니다. MST란 최소비용 신장트리를 의미하며, 무방향 그래프의 간선들에 가중치가 주어진경우, 여러 신장 트리 중에 간선들의 가중치 합이 최소인 신장트리를 의미합니다.

MST를 적용할때는 Kruskal 혹은 Prim을 활용하여 진행할 수 있는데요. 저는 Kruskal 알고리즘을 사용해본 경험이 있어 Kruskal 알고리즘을 적용했습니다. 일반적으로 그래프 내의 간선이 적은경우는 크루스칼을 사용합니다. 크루스칼의 시간복잡도는 O(E log E) 이기에 그렇습니다, 그래프 내의 간선이 많은 경우는 프림 알고리즘 사용합니다. 프림의 시간복잡도는 O(ElogE) 입니다.

 

크루스칼, Kruskal에 대해 좀 더 설명해보자면, 크루스칼의 핵심은 모든 간선을 PriorityQueue를 활용하여 가중치 기준으로 오름차순으로 정렬하고, 이 간선들을 순서대로 모든 정점이 연결될때까지 연결하는 것입니다. 

Union-find 알고리즘을 이용하여 구현할 수 있고, 이를 통해 사이클이 형성되지 않도록 모든 정점을 연결할 수 있습니다.

Union-Find 알고리즘은 O(1) 상수시간복잡도를 가지기에 간선을 정렬하는 로직이 시간복잡도를 좌우하는데, O(E log E)가 크루스칼 알고리즘의 시간복잡도가 됩니다. 여기서 E 는 간선의 개수입니다.

 

코드에 대한 상세정보는 주석에 담아두었습니다.

 

처음에 compareTo 코드를 잘못작성하여 간선이 크기에 의해 올바르게 정렬되지 않아 문제가 있었고, 코드가 길기에 사소한 실수의 디버깅이 힘드므로 집중하여야하는 문제입니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M, K, T;
	public static int answer = 0;
	public static int[] arr;
	public static int[][] map;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static int islandIdx = 2;
	public static boolean[][] visited;
	public static int[][] distanceBetweenIsland;
	public static int[] parent = new int[101]; //부모테이블 초기화하기
	public static PriorityQueue<Edge> pq = new PriorityQueue<>();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	
    	map = new int[N][M];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<M;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
 
    	//각 섬을 Indexing 해줍니다.
    	islandIdx = 2;
    	for(int i = 0; i<N; i++) {
    		for(int j = 0; j< M; j++) {
    			if(map[i][j] == 1) { //만약 섬이라면 Indexing 을 시작합니다.
    				groupingMapBFS(new Node(i, j));
    				islandIdx += 1;
    			}
    		}
    	}
    	
//    	//graph를 구성합니다. 각 섬간에 최단거리를 찾아서 graph 배열에 저장합니다.
    	distanceBetweenIsland = new int[islandIdx][islandIdx];
    	for(int i=2; i<islandIdx; i++) {
    		Arrays.fill(distanceBetweenIsland[i], Integer.MAX_VALUE);
    	}
    	
    	for(int i=0; i<N;i++) {
    		for(int j=0;j<M;j++) {
    			if(map[i][j] >= 2) {
    				//모든 섬의 각 부분에서 실행합니다. 섬이 연결될경우, 안될경우는 findNextIsland에서 다 처리할 것 입니다.
    				findNextIsland(new Node(i, j));	
    			}
    		}
    	}
    	
    	for(int i=2; i<islandIdx; i++) {
    		parent[i] = i;
    	}
    	
    	System.out.println(kruskal());
    	
	}
	
	public static void findNextIsland(Node start) {
		Node temp = start;
		
		int startIslandIdx = map[temp.r][temp.c];
		for(int dir = 0; dir<4; dir++) {
			for(int move=1; ;move++) { //BFS처리.
				int nr = temp.r + dx[dir] * move;
				int nc = temp.c + dy[dir] * move;
 
				//영역 초과할경우 바로 break하여서 중단합니다.
				if(nr < 0 || nr >= N || nc < 0 || nc >= M) break;
 
				//바다일경우 계속해서 move처리할 것 입니다.
				if(map[nr][nc] == 0) { 
					continue;
				}
				
				//같은 섬일경우에는 중단
				else if(map[nr][nc] == startIslandIdx) {
					break;
				}
				
				//다른섬이라면, 거리가 2칸 이상이어야하므로 move > 3 이상부터입니다.
				else if(map[nr][nc] != startIslandIdx){
					//만약 거리가 3 이상. 즉, 다리가 2개이상의 길이라면,
					if(move >= 3) {
						//각 섬과의 최소거리를 갱신시킵니다.
						distanceBetweenIsland[startIslandIdx][map[nr][nc]] = distanceBetweenIsland[map[nr][nc]][startIslandIdx] = Math.min(distanceBetweenIsland[startIslandIdx][map[nr][nc]], move - 1);
						pq.offer(new Edge(startIslandIdx, map[nr][nc], move - 1));
					}
					//만약 거리가 3 미만일경우를 만났을경우에 해당 움직임을 중단한다. 
					if(move < 3 ) break;
					//만약 한번이라도 갱신을 이미했다면 움직임을 중단한다.
					break;
				}
				
			}
		}
	}
	
	public static void groupingMapBFS(Node start) {
		Queue<Node> q = new LinkedList<>();
		q.offer(start);
		map[start.r][start.c]= islandIdx;
		while(!q.isEmpty()) {
			Node temp = q.poll();
			
			for(int dir = 0; dir < 4; dir++) {
				int nr = temp.r + dx[dir];
				int nc = temp.c + dy[dir];
				
				if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
				if(map[nr][nc] != 1) continue; //만약 1이 아닐경우에는 이미 방문한 곳입니다. 
				
				map[nr][nc] = islandIdx;
				q.offer(new Node(nr, nc));
			}
		}
	}
	
	//특정 원소가 속한 집합을 찾습니다.(개선된 서로소 집합 알고리즘)
		public static int findParent(int a) {
			if(parent[a] == a) return a;
			return parent[a] = findParent(parent[a]);
		}
		
		//두 원소가 속한 집합을 합칩니다.
		public static void unionParent(int a, int b) {
			a = findParent(a);
			b = findParent(b);
			if( a < b) parent[b] = a;
			else parent[a] = b;
		}
		
		public static int kruskal() {
			
			int sum = 0;
			int topGroup = parent[2];
			int pqSize = pq.size();
			for(int i=0; i<pqSize;i++) {
				
				Edge edge = pq.poll();
				int a = edge.nodeA;
				int b = edge.nodeB;
				int distance = edge.distance;
//				System.out.println("A:"+a+" b:"+b+" "+distance);
				if(findParent(a) != findParent(b)) {
					unionParent(a, b);
					sum += distance;
				}
			}
//			System.out.println(sum);
			for(int i=2; i<islandIdx; i++) {
				if( topGroup != findParent(parent[i])) {
					return -1;
				}
			}
			return sum;
		}
}
 
class Node{
	int r;
	int c;
	public Node(int r, int c) {
		this.r = r;
		this.c = c;
	}
}
 
class Edge implements Comparable<Edge>{
	int nodeA;
	int nodeB;
	int distance;
	public Edge(int nodeA, int nodeB, int distance) {
		this.nodeA = nodeA;
		this.nodeB = nodeB;
		this.distance = distance;
	}
	
	@Override
	public int compareTo(Edge other) { //거리가 작을수록 우선순위가 높습니다. 오름차순 정렬입니다.
		if(this.distance < other.distance) {
			return -1;
		} else {
			return 1;
		}
	}
}