백준 17472 다리 만들기2

크루스칼 알고리즘을 알고 있었는데도 틀렸던 문제이다..

아직도 그 때 코드가 왜 제대로 동작이 안되었는지 모르겠다..

다시 생각해봐도 크루스칼 코드는 잘 만들었던 것 같은데..

 

혹시나 이 문제를 다시 풀어보면서 몰랐던 부분 때문이었을까 하는 생각도 든다.

문제를 다시 풀면서 알게 된 것은 어짜피 몇 개의 다리를 ArrayList에 넣고 정렬을 하더라도 결국은 N-1개의 edge만 만들면 되기 때문에 만들 수 있는 모든 다리를 다 넣어도 된다는 것이다.

 

저번에 문제를 풀 때는 이러한 생각을 하지 못하고 각 섬을 연결하는 다리 여러 개 중에서 하나만 ArrayList에 넣었었다...

비록 시험에서는 틀렸지만 덕분에 크루스칼에 대해 더 알게 되었다고 생각한다.

 

먼저 2중 for문을 돌면서 안에서 BFS를 통해서 각 섬들을 numbering해준다. Ex. 1번섬, 2번섬

numbering하는 동시에 ArrayList에 모든 좌표를 넣어준다.

이상을 통해서 island라는 ArrayList안에 각 섬의 좌표를 넣은 ArrayList를 넣어준다.

 

그리고 나서 각 섬을 하나씩 꺼내고, 해당 섬으로 부터 다른 섬으로 가면서 나올 수 있는 모든 다리를 

bridge라는 ArrayList에 담는다.

이후, 다리의 길이를 기준으로 정렬하고, Kruskal 알고리즘을 위해서 union-find를 수행한다.

 

만약 모든 union-find가 끝났는데, bridge의 수가 N-1이 되지 않는다면 모든 다리를 연결하지 못한 것이므로 -1을 출력한다.

 

아래는 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main17472 {
	static int ans, n, m;
	static int[] dr = { -1, 0, 1, 0 };
	static int[] dc = { 0, 1, 0, -1 };
	static ArrayList<int[]> bridge;
	static int[][] map;
	static int[] parent;

	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());
			}
		}

		int numbering = 1;
		ArrayList<ArrayList<int[]>> island = new ArrayList<>();
		boolean[][] visit = new boolean[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] != 0 && !visit[i][j]) {//아직 방문하지 않고, 섬인 곳
					//BFS를 돌면서 섬을 ArrayList에 넣는다.
					ArrayList<int[]> thing = new ArrayList<>();
					Queue<int[]> q = new LinkedList<>();
					int[] temp = { i, j };
					q.add(temp);
					thing.add(temp);
					visit[i][j] = true;
					map[i][j] = numbering;

					while (!q.isEmpty()) {
						int[] tt = q.poll();
						int row = tt[0];
						int col = tt[1];

						for (int d = 0; d < 4; d++) {
							int nr = row + dr[d];
							int nc = col + dc[d];

							if (nr < 0 || nr >= n || nc < 0 || nc >= m || visit[nr][nc] || map[nr][nc] == 0)
								continue;
							int[] t = { nr, nc };
							thing.add(t);
							q.add(t);
							visit[nr][nc] = true;
							map[nr][nc] = numbering;
						}
					}
					island.add(thing);//BFS를 통해 구한 하나의 섬을 island 리스트에 넣는다.
					numbering++;//map에도 섬을 표시해준다.(numbering을 통해)
				}
			}
		} // 섬을 다 찾음.

		bridge = new ArrayList<>();
//		for (int i = 0; i < n; i++) {
//			for (int j = 0; j < m; j++) {
//				System.out.print(map[i][j]);
//			}
//			System.out.println();
//		}
//		System.out.println();

		for (int i = 0; i < island.size(); i++) {
			ArrayList<int[]> one = island.get(i);
			getBridge(one);//섬을 하나씩 꺼내서 bridge 리스트에 넣는다.
		}

		//정렬
		Collections.sort(bridge, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[2] - o2[2];
			}
		});
//		for (int[] ttt : bridge) {
//			System.out.println(Arrays.toString(ttt));
//		}

		//union-find를 위한 배열을 만든다.
		parent = new int[island.size() + 1];
		for (int i = 1; i <= island.size(); i++)
			parent[i] = i;

		//union-find 수행
		int cnt = 0;
		for (int i = 0; i < bridge.size(); i++) {
			int a = bridge.get(i)[0];
			int b = bridge.get(i)[1];
			int dis = bridge.get(i)[2];

			if (find(a) != find(b)) {
				union(a, b);
				ans += dis;
				cnt++;
			}
			if (cnt == island.size() - 1)
				break;
		}
		if (cnt != island.size() - 1)
			System.out.println(-1);
		else
			System.out.println(ans);
	}

	private static void union(int a, int b) {
		int x = find(a);
		int y = find(b);

		parent[y] = x;
	}

	private static int find(int a) {
		if (parent[a] == a)
			return a;
		int ret = find(parent[a]);
		parent[a] = ret;
		return ret;
	}

	private static void getBridge(ArrayList<int[]> one) {
		int num = map[one.get(0)[0]][one.get(0)[1]];

		for (int i = 0; i < one.size(); i++) {
			int row = one.get(i)[0];
			int col = one.get(i)[1];

			//4방향을 본다.
			for (int d = 0; d < 4; d++) {
				int dis = 0;
				int nr = row;
				int nc = col;
				while (true) {//섬을 찾을 때까지 가본다.
					nr = nr + dr[d];
					nc = nc + dc[d];
					dis++;
					if (nr < 0 || nr >= n || nc < 0 || nc >= m)
						break;
					if (map[nr][nc] == num)
						break;

					if (map[nr][nc] != 0) {
						if (dis - 1 >= 2) {
							int[] temp = { num, map[nr][nc], dis - 1 };
							bridge.add(temp);
						}
						break;
					}
				}
			}
		}
	}

}