[BOJ][Java] 1976번 여행 가자

문제 설명

 

문제 링크 : https://www.acmicpc.net/problem/1976

 

해당 문제는 유니온 파인드를 사용해야 한다는 것만 알아차리면

나머지는 유니온 파인드를 구현하는 문제이기 때문에 

쉽게 해결할 수 있다.

 

처음에는 각각의 노드의 집합의 대표노드는 자기 자신인 상태를 만든다.

이후 문제에서 들어오는 입력을 잘 받아 union 메서드를 호출한다.

 

예제의 입력대로 1번 노드와 2번 노드가 이어져있기 때문에

2번 노드가 속한 집합의 대표노드를 1로 변경해준다.

 

이후 들어온 입력값으로 3번 노드는 2번 노드와 이어져있으니

여기서도 3번 노드가 속한 집합의 대표노드를 1로 변경해 준다.

 

마지막에 들어오는 입력값을 통해 목적지로 가려고 하는 곳들의

대표노드를 검사하여 모두 동일한 집합이라는 것을 확인하면

"YES" 다르다면 "NO"를 출력해 주면 된다.

 

package boj;

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

public class BOJ1976 {
    static int heads[];
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        heads = new int[N+1];
        for(int i = 0; i < heads.length; i++){
            heads[i] = i;
        }

        for(int i = 1; i <= N; i++){
            int[] temp = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();

            for(int j = 0; j < temp.length; j++){
                if(temp[j] == 1) union(i, j+1);
            }
        }

        boolean flag = true;
        int head = 0;
        int[] targets = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        head = find(targets[0]);

        for(int num: targets){
            if(head != find(num)){
                flag = false;
                break;
            }
        }

        if(flag) System.out.println("YES");
        else System.out.println("NO");

    }
    static void union(int a, int b){
        int aHead = find(a);
        int bHead = find(b);

        if(aHead != bHead) heads[bHead] = aHead;
    }

    static int find(int node){
        if(node == heads[node]) return node;
        return heads[node] = find(heads[node]);
    }
}