[백준] 1976 - 여행 가자

[문제링크]

1976번: 여행 가자

 

0. 1717번 문제처럼 disjoint set의 이용 (2021.04.28 - [백준/골드] - [백준] 1717 - 집합의 표현)

 

1. 모든 연결된 x,y쌍에 대해 그 집합을 합쳐준다

 

2. 모든 방문할 node들에 대해 같은 집합에 속하는지 확인한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		N = pint(br.readLine());
		M = pint(br.readLine());
		init();
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int x = pint(st.nextToken());
				if(x==1) {
					mergeGroup(i,j);
				}
			}
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int root = getRoot(pint(st.nextToken())-1);
		boolean possible=true;
		for (int i = 1; i < M; i++) {
			if( root != getRoot( pint(st.nextToken())-1 ) )possible=false;
		}
		System.out.println(possible?"YES":"NO");
		
	}
	static int N,M;
	static int[]parents;
	
	static void init() {
		parents=new int[N];
		for (int i = 0; i < N; i++) {
			parents[i]=i;
		}
	}

	static int getRoot(int x) {
		if(parents[x]!=x)return parents[x]=getRoot(parents[x]);
		else return x;
	}
	
	static void mergeGroup(int x, int y) {
		parents[getRoot(y)]=getRoot(x);
	}
	
	static boolean isSameGroup(int x, int y) {
		return getRoot(x)==getRoot(y);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면