[BOJ_1976] 여행 가자

설명

---

단순히 분리집합을 구현하여서 해당 위치가 같은 합집합에 속하는지 판단하는 것인데 이를 플로이드 와셜과 개념적으로 흔들리면 플로이드 와셜로 접근 할 수 있습니다. 다만, 해당 문제는 분리집합을 사용하여 N개 이상의 위치에 대해서 해당 위치가 처음 골라진 root 위치와 같아야 같은 곳을 통해서 지나 갈 수 있으므로 이를 모든 케이스에 대해서 다 점검하기에 단순히 1 -> N 어디로 간다의 로직을 짜는 플로이드 와셜과는 확실하게 다른 문제입니다.

 

코드

---

package BOJ.disjoint_set;

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

public class BOJ_1976 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        int N = Integer.parseInt(tk.nextToken());

        int[] parent = new int[N + 1];

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

        int M = Integer.parseInt(in.readLine());
        for (int i = 0; i < N; i++){
            tk = new StringTokenizer(in.readLine()," ");
            int size = tk.countTokens();
            for (int j = 0; j < size; j++){
                if(Integer.parseInt(tk.nextToken()) == 1){
                    union(i + 1, j + 1,parent);
                }
            }
        }

        tk = new StringTokenizer(in.readLine(), " ");
        int[] plan = new int[M];
        for (int i = 0; i < M; i++) {
            plan[i] = Integer.parseInt(tk.nextToken());
        }

        boolean possible = true;
        int root = getParent(parent, plan[0]);
        for (int i = 1; i < M; i++) {
            if (getParent(parent, plan[i]) != root) {
                possible = false;
                break;
            }
        }

        if (possible) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
    private static int getParent(int[] parent, int x){
        if(parent[x] == x){
            return x;
        }
        return parent[x] = getParent(parent, parent[x]);
    }

    private static void union(int x, int y, int[] parent) {
        int rootA = getParent(parent,x);
        int rootB = getParent(parent,y);
        parent[rootB] = rootA;
    }
}

 

문제 링크

1976번: 여행 가자 (acmicpc.net)