BOJ 1976 여행 가자

import java.io.*;
import java.util.*;
public class Main {
	private static int[][]city;
	private static int[]root;
	private static int[]rank;
	private static int[]travel;
	public static void main(String[] args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); //도시 개수
		st = new StringTokenizer(br.readLine());
		int m = Integer.parseInt(st.nextToken()); //여행 갈 도시 개수
		city = new int[n+1][n+1];  // 도시정보입력 
		travel=new int[m];  // 여행갈 루트 입력 
		root = new int[n+1]; 
		rank=new int[n+1];
		for(int i=1; i<=n; i++) {
			root[i]=i; //root 자기 자신으로 설정 
			rank[i]=0; //rank 초기화 
		}
		String[]s;
		for(int i=1; i<=n; i++) {
			s = br.readLine().split(" ");
			for(int j=1; j<=n; j++) {
				city[i][j]=Integer.parseInt(s[j-1]); //각각 도시 정보입력 
				if(city[i][j]==1) union(i,j);
			}
		}
		s = br.readLine().split(" ");
		boolean unavail=false;
		for(int i = 0; i<m;i++) {
			travel[i]=Integer.parseInt(s[i]); //여행갈 루트 입력 
		}
		int first = find(travel[0]);
		for(int i=1; i<m;i++) {
			if(find(travel[i])!=first) {
				System.out.println("NO");
				unavail=true;
				break;
			}
		}
		if(!unavail) System.out.println("YES");
	}
	
	private static void union(int x , int y) { //두개 합치기 
		x = find(x);
		y = find(y);
		if(x==y) return;
		if(rank[x]<rank[y]) {
			root[x]=y;
			rank[x]+=rank[y];
		}
		else {
			root[y]=x;
			rank[y]+=rank[x];
		}	
	}
	private static int find(int x) { //x의 루트값 반환 
		if(root[x]==x) return x;
		else {
			return root[x]=find(root[x]);
		}
	}	
}

1976번: 여행 가자

disjoint set 알고리즘만 알고있다면 쉽게 풀 수 있는 문제이다. 여행 경로가 주어졌을 때, 다른 경로를 거쳐서or 바로 해당 경로에 도달 할 수 있으면 YES를, 아니면 NO를 출력하는 것이다 . 

따라서, union find 알고리즘으로 서로 연결되어 있는 모든 경로들을 union 해주면 된다.

여기서 A도시에서 B도시까지 갈 수 있는가 없는가는 A도시의 최고 꼭대기에 있는 부모와 B도시의 최고 꼭대기에 있는 부모가 같은지 아닌지를 판별하면된다. 

(union find를 통해서 이어져있는 도시들은 모두 같은 최고 꼭대기 부모를 갖게 되므로)

따라서 이를 주어진 경로에 대해 검사해주다가, 부모가 다른 도시가 나올 경우 NO를 출력해주면 된다.