[Java/자바 백준 1976] 여행가자

풀이

유니온 파인드 문제 

 

문제 핵심은 연결되었는지에 대해 물어보는 문제

매개체 도시가 있어서 1 - 3 도시가 서로 연결 되어있지 않아도

1 - 2 - 3 이 연결 되었으면 연결된 것 !

 

parents 배열을 만들어주고 먼저 자기 자신을 부모로 갖게 설정한 뒤,

입력을 받으면서 1인 경우(연결된 경우)에 한해서 유니온 파인드를 적용해주었습니다.

 

연결된 경우 이므로 a, b 둘중 인덱스가 큰 숫자를 작은 인덱스에 자식으로 갖게 만들어주었습니다.

 

ex) union (0, 4) 일경우

왼쪽이 적용 전, 오른쪽이 적용 후

이 상태에서 union (2,4)가 들어온다면 

aRoot = 2 이지만

bRoot는 4 -> 0 이므로 bRoot = 0이 됩니다.

그렇다면 parents 배열은 이런식으로 바뀌겠죠 !

 

유니온 파인드를 모두 적용 시킨 후,

정해진 여행 계획에서 다른 parents값을 가진 다면 NO

같다면 YES로 출력 !

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

public class Main {
	static int N, M;
	static int[] parents;
	static int[] root;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		make();
		
		root = new int[M];
		for(int i = 0 ; i < N ; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j < N ; j++) {
				int temp = Integer.parseInt(st.nextToken());
				if(temp == 1) union(i, j);
			}
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < M ; i++) {
			root[i] = Integer.parseInt(st.nextToken()) - 1;
		}
		
		boolean flag = true;
		
		for(int i = 1 ; i < M ; i++) {
			if(parents[root[i]] != parents[root[i-1]]) flag = false;
		}
		
		if(flag) System.out.println("YES");
		else System.out.println("NO");
	}
	
	private static void union(int a, int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		
		if(aRoot < bRoot) parents[bRoot] = aRoot;
		else if(aRoot > bRoot) parents[aRoot] = bRoot;
	}
	
	private static int find(int a) {
		if(a == parents[a]) return a;
		return parents[a] = find(parents[a]);
	}
	
	private static void make() {
		parents = new int[N];
		for(int i = 0; i < N ; i++) {
			parents[i] = i;
		}
	}

}