[BOJ]1976번 : 여행 가자

https://www.acmicpc.net/problem/1976

1976번: 여행 가자

분류 : DisJoint-Set

 

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

class MyScanner {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }
}

public class Main {

    static PrintWriter out;
    //root[a] = b -> a의 부모는 b이다.
    static int[] root = new int[1001];
    public static void main(String[] args) throws IOException {
        MyScanner sc = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));
        int N = sc.nextInt();
        int M = sc.nextInt();
        // root 초기화
        for (int i = 1; i <= N; i++)
        {
            root[i] = i;
        }
        
        for(int A = 1;A<=N;A++)
        {
            for(int B = 1;B<=N;B++)
            {
                int num =sc.nextInt();
                if(num ==1)
                {
                    Union(A,B);
                }
            }
        }
        int ex = sc.nextInt();
        int Test =Find(ex);
        String str = "YES";
        for(int i=0;i<M-1;i++)
        {
            int T = sc.nextInt();
            T=Find(T);
            if(T!=Test)
            {
                str= "NO";
                break;
            }
        }
        out.println(str);
        out.flush();
    }
    private static void Union(int a, int b) {
        a = Find(a);
        b = Find(b);
        if (a != b) {
            root[a] = b;
        }
    }
    private static int Find(int k) {
        //루트 노드 이면 return k
        if (k == root[k])
            return k;
        //그 외에는 자신의 루트를 찾으러 간다.
        return root[k] = Find(root[k]);

    }
}

1717번 : 집합의 표현과 마찬가지로 Union-Find 알고리즘을 이해하기에 좋은 문제

마지막 줄 여행 계획 비교 하는 부분만 주의하면 1717번 문제와 기본 틀은 거의 비슷하다.