[백준 BOJ] 17472 다리 만들기2(MST, BFS) - 자바

문제 접근 방법

1. 먼저 각 섬들에 대해 번호를 부여해줍니다. (BFS)

저는 인접한 섬들에 대해 같은 번호를 부여하도록 하였습니다.

섬에 대한 그룹핑

 

2. 다리 놓기(이중 for문)

각 섬들 사이의 거리를 구하기 위해 저는 모든 행과 열을 탐색하였습니다. 섬과 섬 사이의 0의 개수를 카운트한 다음 이에 대해 Math.min을 통해 최소 다리 길이를 구하였습니다.

 

 

 

3. 모든 섬을 연결하는 다리 길이의 최솟값 구하기(MST - 크루스칼 알고리즘)

각 섬에 대한 최소 다리 길이를 구했다면, 이제 모든 섬을 연결할 수 있는지 확인해야 합니다. 특히 이때 MST 알고리즘 중에서 저는 크루스칼 알고리즘을 사용하였습니다. 또한, 최소 길이를 구하는 것이기 때문에 우선 순위 큐를 통해 다리 길이가 작은 순서대로 정렬시켰습니다. 우선 순위 큐에서 하나씩 노드를 poll 해보면서 각 섬들을 연결시킵니다.  이 연결시킨 섬들의 개수가 1번에서 부여한 그룹 개수 - 1이 아닌 경우 모든 섬을 연결시키지 못했으므로 -1을 출력하게 됩니다.

 

 

 

주의할 점

각 섬들간의 다리 길이를 구할 때  'ㄷ'자 유형의 섬에 대한 조건을 추가해줘야 합니다. 이 조건을 빼먹어 10%정도에서 계속 틀렸습니다.  따라서, 저는 else if(to == from)인 경우에 대한 조건을 추가하였습니다.

 

반례

 

 

 

구현 소스

/*
 * boj 17472 다리 만들기2
 * 출력 : 모든 섬을 연결하는 다리 길이의 최솟값, 모든 섬을 연결하는 것이 불가능하면 -1
 * */
public class Main_17472{

	static int[][] maps;
	static int N, M;
	static int[][] depths;//그룹핑된 섬 정보 저장
	static boolean[][] visited;
	static int[][] paths;//다리 길이
	
	static int[] parents;//부모 인덱스
	
	
	static class Node implements Comparable<Node> {
		int from, to, weight;

		
		public Node(int from, int to, int weight) {
			super();
			this.from = from;
			this.to = to;
			this.weight = weight;
		}


		@Override
		public int compareTo(Node o) {
			return this.weight - o.weight;
		}
		
		
	}

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

		maps = new int[N][M];
		depths = new int[N][M];
		visited = new boolean[N][M];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				maps[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		//1. 각 섬을 구분하기 위한 섬 그룹핑
		int groupCnt = 1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (!visited[i][j] && maps[i][j] == 1) {
					grouping(i, j, groupCnt);
					groupCnt++;
				}
			}
		}
		
		
		/*for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(depths[i][j] + " ");
			}
			System.out.println();
		}
		*/
		
		//2. 각 섬 사이의 다리 길이를 구함
		paths = new int[groupCnt][groupCnt];//다리 길이 저장
		
		for (int i = 1; i < groupCnt; i++) {
			Arrays.fill(paths[i], Integer.MAX_VALUE);
		}
		
		searchAllPath();
		
		/*for (int i = 1; i < groupCnt; i++) {
			for (int j = 1; j < groupCnt; j++) {
				System.out.print("(" + i + "," + j + ") = " + paths[i][j] + " ");
			}
			System.out.println();
		}*/
		
		//3. MST를 통해 최소 다리 길이를 구함
		ArrayList<ArrayList<Node>> lists = new ArrayList<>();
		
		for (int i = 1; i < groupCnt; i++) {
			lists.add(new ArrayList<Node>());
		}
		
		PriorityQueue<Node> pq = new PriorityQueue<Node>();

		for (int from = 1; from < groupCnt; from++) {
			for (int to = 1; to < groupCnt; to++) {
				if(paths[from][to] == Integer.MAX_VALUE) continue;
				pq.add(new Node(from, to, paths[from][to]));
			}
		}
		
		int result = 0;
		
		make(groupCnt);

		int size = pq.size();
		int connectCnt = 1;
		for (int i = 0; i < size; i++) {
			Node node = pq.poll();
			if(find(node.from) != find(node.to)) {//다리를 연결 시킴
				result += node.weight;
				union(node.from, node.to);
				connectCnt++;
			}
		}
		
		//연결되지 않는 경우도 확인		
		if(connectCnt != groupCnt-1 || result == 0)
			result = -1;
			
		System.out.println(result);
	}

	static int[][] dir = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };// 상하좌우

	// 섬에 대한 그룹핑
	static void grouping(int r, int c, int groupNum) {
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] { r, c });

		while (!queue.isEmpty()) {
			int[] tmp = queue.poll();
			int nowX = tmp[0];
			int nowY = tmp[1];

			if (visited[nowX][nowY])
				continue;

			depths[nowX][nowY] = groupNum;

			visited[nowX][nowY] = true;
			for (int i = 0; i < dir.length; i++) {
				int nextX = nowX + dir[i][0];
				int nextY = nowY + dir[i][1];

				if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M) continue;
				if (visited[nextX][nextY]) continue;

				if (maps[nextX][nextY] == 1) {
					depths[nextX][nextY] = groupNum;
					queue.add(new int[] { nextX, nextY });
				}
			}
		}
	}

	
	//각 섬간의 길이를 구함
	static void searchAllPath() {
		int from = 0;
		
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < M; c++) {
				if(depths[r][c] == 0) continue;
				from = depths[r][c];	
				connect(from, r, c);
			}
		}
		
	}
	
	//다리 연결 시킴
	static void connect(int from, int r, int c) {
		int cnt = 0;
		for (int nc = c+1; nc < M; nc++) {
			int to = depths[r][nc];
			if(to == 0) cnt++;
			else if(to == from) {
				if(cnt > 0) break;//반례 : 'ㄷ'자 섬인 경우
				else continue;
			}else if(to != from){//다른 섬을 만난 경우
				if(cnt <= 1) break;
				paths[from][to] = Math.min(paths[from][to], cnt);
				paths[to][from] =  Math.min(paths[from][to], cnt);
				break;
			}
		}
		
		//열
		cnt = 0;
		for (int nr = r+1; nr < N; nr++) {
			int to = depths[nr][c];
			if(to == 0) cnt++;
			else if(to == from) {
				if(cnt > 0) break;
				else continue;
			}else if(to != from){
				if(cnt <= 1) break;
				paths[to][from] = Math.min(paths[to][from], cnt);
				paths[from][to] = Math.min(paths[to][from], cnt);
				break;
			}
		}
	}
	
	

	
	///////////////////크루스칼 알고리즘////////////////////////////////
	
	static void make(int groupCnt) {
		parents = new int[groupCnt];
		for (int i = 1; i < groupCnt; i++) {//자기 자신을 부모로 설정
			parents[i] = i;
		}
	}
	
	static boolean union(int a, int b) {
		int a_root = find(a);
		int b_root = find(b);
		
		if(a_root == b_root) return false;
		
		parents[b_root] = a_root;
		
		return true;
	}
	
	static int find(int a) {
		if(parents[a] == a) {
			return a;
		}
		return parents[a] = find(parents[a]);
	}
	
	
	
}