백준 1976번 : 여행 가자 java

이 문제는 분리 집합을 이용하여 푸는 문제입니다.

분리 집합이란 여러 개의 분리된 집합들이 있을 때 이 집합들에 대한 연결 관계를 입력받아 연결하여 이를 이용하는
문제입니다.

이 문제에서는 N개의 도시에 대한 연결 관계를 입력받아서 M개의 도시를 여행할 수 있는지 확인하는 문제입니다.

한번 갔던 도시라도 연결되어 있기만 하다면 갈 수 있습니다.

코드를 바로 보여드리도록 하겠습니다.

---

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

public class Main {
    static int[] parent;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        parent = new int[N];
        for(int i = 0; i<N; i++)
            parent[i] = i;

        for(int i = 0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            for(int j = 0; j<N; j++){
                int num = Integer.parseInt(st.nextToken());

                if(num == 1)
                    union(i, j);
            }
        }

        int[] trip = new int[M];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i<M; i++)
            trip[i] = Integer.parseInt(st.nextToken())-1;

        boolean canGo = true;
        for(int i = 0; i<M-1; i++){
            if(union(trip[i], trip[i+1]))
                canGo = false;
        }

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

    static int find(int idx){
        if(parent[idx] == idx)
            return idx;
        else
            return find(parent[idx]);
    }
    static boolean union(int idx1, int idx2){
        int parent1 = find(idx1);
        int parent2 = find(idx2);

        if(parent1 == parent2)
            return false;
        else{
            parent[parent2] = parent1;
            return true;
        }
    }
}

union-find를 이용하여 분리 집합을 구현하였습니다.