[PS] 백준 17472 : 다리 만들기 2

문제

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

17472번: 다리 만들기 2

해설

 

다리만들기 문제는 BFS와 MST 을 만드는 알고리즘을 이용해서 문제를 해결 할 수 있습니다. MST를 만드는 알고리즘에 대한 설명은 다음 블로그 링크를 참조해주세요. 

 

문제는 크게 두 부분으로 나뉘어 집니다. 

 

1. 바다를 제외한 연결된 영역을 같은 섬 영역으로 표시하고 각 섬마다 구분 지어 주기

 

2. 각 섬에서 다른 섬까지 이어지는 경로 찾기

 

1번의 경우 일반적인 BFS를 통해 해결할 수 있습니다. 2번의 경우 모든 방향을 고려할 필요 없이 한 정점에서 오른쪽으로 탐색하는 방향은 그와 만나는 다른 정점에서 왼쪽으로 탐색하는 경우와 결과가 같으므로 각 정점에서 오른쪽과 아래쪽으로 이동하는 경우만 고려하여 문제를 해결할 수 있습니다.

 

위의 두 가지 경우를 모두 처리한다면 Kruskal 이나 Prim 알고리즘을 사용해서 문제를 쉽게 해결할 수 있습니다. 

 

코드

/** 
* 알고리즘 : kruskal
*/
public class BOJ_17472_다리_만들기_2 {
	static StringBuilder sb = new StringBuilder();
	static int n, m;
	static int[][] map;
	static int[] group;
	static boolean[][] visit;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	
	
	static class Edge implements Comparable<Edge>{
		int u, v, c;

		public Edge(int u, int v, int c) {
			this.u = u;
			this.v = v;
			this.c = c;
		}

		@Override
		public int compareTo(Edge e) {
			// TODO Auto-generated method stub
			return this.c - e.c;
		}
	}
	
	static int find(int u) {
		if(group[u] < 0) return u;
		return group[u] = find(group[u]);
	}
	
	static boolean union(int u, int v) {
		u = find(u); v = find(v);
		if(u == v) return false;
		group[v] = u;
		return true;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
	
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		
		map = new int[n][m];
		visit = new boolean[n][m];
		group = new int[7];
		Arrays.fill(group, -1);
		
		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());
			}
		}
		
		int color = 0;
		// 인접한 영역을 같은 섬으로 표시한다.
		Queue<int[]> q = new LinkedList<>();
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<m; j++) {
				if(visit[i][j] || map[i][j] <= 0) continue;
				color += 1;
				visit[i][j] = true;
				q.add(new int[] {i, j});
				while(!q.isEmpty()) {
					int[] pos = q.poll();
					map[pos[0]][pos[1]] = color;
					for(int dir = 0; dir<4; dir++) {
						int nx = pos[0] + dx[dir];
						int ny = pos[1] + dy[dir];
						if(nx < 0 || nx >= n || ny < 0 || ny >= m || visit[nx][ny] || map[nx][ny] <= 0) continue;
						visit[nx][ny] = true;
						q.add(new int[] {nx, ny});
					}
				} // while()
			} // for(j)
		} // for(i)
		
		// 한 좌표에서 이동할 수 있는 방향은 중복을 제거하기 위해서 오른쪽과 아래 방향만 고려하면 되므로 
		// 각각의 좌표에서 오른쪽과 아래쪽으로 이동했을 때 다른 섬이 발견되는 경우 이 때 거리가 1 보다 클 경우
		// 각각의 섬의 번호를 정점으로 하여금 간선 정보를 우선순위 큐에 업데이트 한다.
		PriorityQueue<Edge> pq = new PriorityQueue<>();
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<m; j++) {
				if(map[i][j] > 0) {
					for(int r = i + 1; r < n; r++) {
						if(map[r][j] > 0) {
							if(map[i][j] != map[r][j] && r - i - 1 > 1)
								pq.add(new Edge(map[i][j], map[r][j], r - i - 1));
							break;
						}
					}
					
					for(int c = j + 1; c < m; c++) {
						if(map[i][c] > 0) {
							if(map[i][j] != map[i][c] && c - j - 1 > 1) 
								pq.add(new Edge(map[i][j], map[i][c], c - j - 1));
							break;
						}
					}
				}
			} // for(j)
		} // for(i)
		
		int edge = 0;
		int cost = 0;
		// 크루스칼 알고리즘 수행
		while(!pq.isEmpty()) {
			if(edge == color - 1) break;
			Edge e = pq.poll();
			if(union(e.u, e.v)) {
				cost += e.c;
				edge += 1;
			}
		}
		System.out.println((edge == color - 1 ? cost : -1));
	}
}