Do it! 알고리즘 코딩 테스트 (51번)

51번 여행 가자

---

내가 떠올린 풀이 해설

도시 연결 유무를 유니온 파인드 연산을 이용해 해결할 수 있다는 아이디어를 떠올릴 수 있으면 쉽게 해결된다.

일반적으로 유니온 파인드는 그래프에서 많이 활용되지만, 위 문제와 같이 단독으로 활용할 수 있다는 점도 참고해야 된다.

인접 행렬을 탐색하면서 연결될 때마다 union연산을 수행하는 방식으로 풀어가면 된다. 도시와 여행 경로를 저장하고 각 노드와 관련된 대표 노드 배열의 값을 초기화한다. 도시 연결 정보가 저장된 인접 행렬을 탐색하면서 도시가 연결돼 있을 때 union연산을 수행한다. 이때 항상 큰 도시가 대표도시가 되도록 union 연산의 매개변수를 변경한다. 마지막으로 여행 경로에 포함된 도시의 대표 노드가 모두 같은지 확인한 후 출력하면 된다.

---

정확한 풀이 

import java.util.*;
import java.io.*;

public class Baek1976 {
	static int[] parent;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		int[][] arr = new int[n + 1][n + 1];
		for(int i = 1; i <= n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 1; j <= n; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int[] route = new int[m + 1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 1; i <= m; i++) {
			route[i] = Integer.parseInt(st.nextToken());
		}
		
		parent = new int[n + 1];
		for(int i = 1; i <= n; i++) {
			parent[i] = i;
		}
		
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(arr[i][j] == 1) {
					union(i, j);
				}
			}
		}
		// 여행 계획 도시들이 1개의 대표 도시로 연결돼 있는지 확인하기 
		int index = find(route[1]);
		for(int i = 2; i < route.length; i++) {
			if(index != find(route[i])) {
				System.out.println("NO");
				return;
			}
		}
		System.out.println("YES");
	}

	private static void union(int i, int j) {
		i = find(i);
		j = find(j);
		if(i != j) {
			parent[j] = i;
		}
	}

	private static int find(int j) {
		if(parent[j] == j) {
			return j;
		}
		else {
			return parent[j] = find(parent[j]);
		}
	}
}

---

오늘의 회고

오늘은 union find 문제를 풀었습니다. 오늘까지 해서 복습은 마무리되었습니다. 복습으로 느낀 점은 알고리즘을 대비할 때 문제를 많이 풀려고 하지 말고 하나를 풀더라도 정확하게 이해하고 풀어야 한다고 느꼈습니다. 복습하면서 다시 푸는데 안 풀리는 문제들도 많았고 이해를 하면서 내 것으로 만드는 과정을 가지겠습니다.