여행가자_1976

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

분리집합 문제이다

각 여행지에 대해서 최고 부모 여행지를 찾아서 비교하고 만약 최고 부모 여행지가 다른데 connect되어 있다고 하면 union을 해준다

union을 진행할 때는 이미 i, j에 대해서 find()를 진행하였으므로 그냥 저 작은(최고 부모 자격이있는) 여행지의 부모를 그렇지 않은 여행지의 최고 부모로 바꿔준다 그러면 i, j는 동일한 최고 부모 여행지를 갖게 되고 연결된 상태가 된다

find를 할 때는 자신이 가르키는 여행지가 자기인지 보고 아니면 재귀로 자신의 부모여행지를 계속 찾아가면서 최고 부모노드에 들어가면 나머지 여행지들에게 해당 최고 부모노드를 적어주는 방식으로 한다

package Gold이상문제_정리;

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

public class 여행가자_1976{
    static int[] p = new int[201];
    static int N, M;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        for (int i = 1; i <= N; i++)
            p[i] = i;

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                if (Integer.parseInt(st.nextToken()) == 1 && i < j) {
                    if (find(i) != find(j))
                        union(i, j);
                }
            }
        }

        st = new StringTokenizer(br.readLine());
        int top = 0;
        int city;
        for (int i = 0; i < M; i++) {
            city = Integer.parseInt(st.nextToken());
            if (top == 0)
                top = find(city);
            else {
                if (top != find(city)) {
                    System.out.println("NO");
                    return;
                }
            }
        }
        System.out.println("YES");
    }

    private static void union(int i, int j) {
        p[p[j]] = p[i];
    }

    private static int find(int city) {
        if (p[city] == city)
            return city;
        return p[city] = find(p[city]);
    }
}