/ BOJ

BOJ_1976_여행가자_JAVA

문제 : 여행가자

링크 : BOJ_1976_여행가자

접근 방식

서로소 집합을 구현하여 그 기능인 union과 findSet를 이용한다.

일단 각각 분리된 집합을 1~N까지 생성한다. 서로소 집합의 makeSet에 해당한다.

서로소 집합을 생성했으면, 입력값을 읽어와서 union 메서드를 통해 같은 집합으로 합친다(합집합).

합집합화 시키는 작업을 마치고 나면 주어진 경로를 findSet을 통해 같은 집합에 속해있는지 확인한다.

같은 집합에 속해있으면 이어져 있는 여행경로이기 때문에 YES를, 같은 집합에 속해있지 않다면 NO를 출력하고 시스템을 종료한다.

소스 코드

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

public class BOJ_1976_여행가자 {

	static int[] parents;

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());
        int M = Integer.parseInt(in.readLine());

        makeSet(N);

        StringTokenizer st;
        for(int i=1;i<=N;i++) {
        	st = new StringTokenizer(in.readLine()," ");
        	for(int j=1;j<=N;j++) {
        		int num = Integer.parseInt(st.nextToken());
        		if(num == 1) {
        			union(i,j);
        		}
        	}
        }

        st = new StringTokenizer(in.readLine()," ");
        int start = findSet(Integer.parseInt(st.nextToken()));
        for(int i=1;i<M;i++) {
        	int inNum = Integer.parseInt(st.nextToken());

        	if(start != findSet(inNum)) {
        		System.out.println("NO");
        		return;
        	}
        }

        System.out.println("YES");
	}


	static boolean union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);

		if(aRoot == bRoot) {
			return false;
		}

		parents[bRoot] = aRoot;
		return true;
	}

	static int findSet(int a) {

		if(a == parents[a]) {
			return a;
		} else {
			return parents[a] = findSet(parents[a]);
		}
	}

	public static void makeSet(int N) {
		parents = new int[N+1];

		for(int i=1;i<=N;i++) {
			parents[i] = i;
		}

	}
}