🔗 Problem

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

👩‍💻 Code

package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

// 여행 가자

public class BJ1976 {
	
	static int num;
	static int numDest;
	static int[] dest;
	static int[] parent;
	static int root;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		num = Integer.parseInt(br.readLine());
		numDest = Integer.parseInt(br.readLine());
		parent = new int[num+1];
		
		for(int i = 1; i <= num; i++) {
			parent[i] = i;
		}
		
		// union
		StringTokenizer st;
		for(int i = 1; i <= num; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 1; j <= num; j++) {
				if(Integer.parseInt(st.nextToken()) == 1) {
					if(i == j) continue;
					union(i, j);
				}
			}
		}
		
		// find
		st = new StringTokenizer(br.readLine());
		
		for(int i = 0; i < numDest; i++) {
			int city = Integer.parseInt(st.nextToken());
			if(i == 0) {
				root = findParent(city);
				continue;
			}
			if(root != findParent(city)) {
				System.out.println("NO");
				System.exit(0);
			}
		}
		System.out.println("YES");
	}
	
	private static void union(int a, int b) {
		
		a = findParent(a);
		b = findParent(b);
		
		if(a != b) {
			if(a < b) parent[b] = a;
			else parent[a] = b;
		}
	}
	
	private static int findParent(int x) {
		if(x == parent[x]) return x;
		return findParent(parent[x]);
	}

}

📌 Note

아이디어

• union()에서 마지막으로 찾은 root에 대해서 갱신해야 한다!
• 처음에 연결되어 있기만 하면 parent를 같게 설정해서 틀렸습니다
• 꼼꼼하게 생각하고 구현하자.

재귀 호출

• 같은 Union Find 문제인 #1717에서는 findParent()에서

  return parent[x] = findParent(parent[x]);

  압축 최적화를 위해 위와 같이 return 하였는데,
  이 문제는 이미 parent가 들어가 있기에 굳이 parent를 넣어줄 필요가 없다.
  (나중에 재사용 x)