[백준] 여행 가자 1976 java - union find

일단 처음에 문제가 잘 이해가 가지 않아서 오래 걸렸다..

도시의 개수 N이 연결되어 있는지의 대한 정보가 N*N개 입력,

여행 계획에 대한 정보를 M개 입력하는 것이다..

또한 순간 착각해서 A->B, B->A를 같은 경우로 생각해서 ArrayList에 양방향으로 추가해줬는데..

다른 경우이므로 따로 List에 추가해주지 않아도 된다 !!

 

이 문제는 bfs로 풀이해도 되지만

union-find 알고리즘으로 푸는 게 더 수월하다 !

 

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

 

 

 

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

public class Main {
    static int N, M;
    static int[] parent;

    static void union(int x, int y){
        x = find(x);
        y = find(y);

        if(x>y) parent[x] = y;
        else parent[y] = x;
    }
    static int find(int x){
        if(x==parent[x])
            return x;
        return parent[x] = find(parent[x]);
    }

    public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = null;

            N = Integer.parseInt(br.readLine());
            M = Integer.parseInt(br.readLine());
            parent = new int[N+1];

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


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

            int[] city = new int[M+1];
            st = new StringTokenizer(br.readLine());
            for(int i=1;i<=M;i++){
                city[i] = Integer.parseInt(st.nextToken());
            }

            boolean flag = true;
            for(int i=1;i<=M-1;i++){
                if(parent[city[i]]!=parent[city[i+1]]){
                    flag = false;
                    break;
                }
            }

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

    }
}