[devmoon] 백준 1976 - (java)여행 가자

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

1976번: 여행 가자

1. 유형

union-find

 

2. 시뮬레이션

하나하나 다음 노드가 연결됐는지 확인하는 문제가 아니다.

경로가 한 덩어리로 이어져 있는지만 확인하면 된다.

 

따라서 각 노드의 "최고"부모노드가 전부 같으면, 노드가 전부 연결 돼있다는 의미.

 

부모노드를 구하기 위해 union-find알고리즘을 활용

 

3. 코드

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

public class Main {
	static int N, M;
	static int p[];
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		N = stoi(st.nextToken());
		st = new StringTokenizer(bf.readLine());
		M = stoi(st.nextToken());
		p = new int[N+1];
		for(int i=0; i<=N; i++)
			p[i]=i;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 0; j < N; j++) {
				int k = stoi(st.nextToken());
				if(k==1) {
					union(i+1, j+1);
				}
			}
		}
		st = new StringTokenizer(bf.readLine());
		int ans[] = new int[M];
		boolean flag= true;
		for(int i=0; i<M; i++) {
			ans[i] = find(stoi(st.nextToken()));
			if(i==0) continue;
			if(ans[i] != ans[i-1]) {
				flag= false;
			}
		}
		if(flag)
			System.out.println("YES");
		else
			System.out.println("NO");
	}
	static int stoi(String s) {
		return Integer.valueOf(s);
	}
	static void union(int fir, int sec) {
		fir = find(p[fir]);
		sec = find(p[sec]);
		if(fir > sec)
			p[fir] = sec;
		else
			p[sec] = fir;
	}
	static int find(int node) {
		if(p[node] == node) {
			return node;
		}
		return p[node]= find(p[node]);
	}
	
}

4. 느낀점

union-find의 정석같은 문제