[BOJ] 1976. 여행 가자

문제 원본 : https://www.acmicpc.net/problem/1976

1976번: 여행 가자

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

public class Main {
    static int[] parent;
    static int[] depth;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        parent = new int[n + 1];
        depth = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            parent[i] = i;
        }

        StringTokenizer st;
        for (int i = 1; i <= n; ++i) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; ++j) {
                if (st.nextToken().equals("1")) {
                    union(i, j);
                }
            }
        }

        st = new StringTokenizer(br.readLine());
        int city = Integer.parseInt(st.nextToken());
        boolean possible = true;
        for (int i = 1; i < m; ++i) {
            if (find(city) != find(Integer.parseInt(st.nextToken()))) {
                possible = false;
            }
        }

        bw.write(possible ? "YES" : "NO");

        bw.close();
        br.close();
    }

    public static int find(int u) {
        if (u == parent[u]) {
            return u;
        }

        return parent[u] = find(parent[u]);
    }

    public static void union(int u, int v) {
        u = find(u);
        v = find(v);

        if (u == v) {
            return;
        }

        if (depth[u] > depth[v]) {
            int tmp = u;
            u = v;
            v = tmp;
        }

        parent[u] = v;

        if (depth[u] == depth[v]) {
            ++depth[v];
        }
    }
}

• 유니온-파인드 문제
• 도시가 연결되어 있으면 합쳐주고(union) 여행 계획도시가 전부 연결되어 있는지 체크하면 된다.