[BOJ] 1976번 여행가자 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * 여행가자
 */
public class Main {
    static int N, M;
    static int[] parent, plan;

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

        parent = new int[N+1];
        plan = new int[M];

        initParent();

        updateParent(br);

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

        for (int i = 1; i < M; i++) {
            if (find(plan[i]) != find(plan[i-1])) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");

    }

    private static void updateParent(BufferedReader br) throws IOException {
        StringTokenizer st;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                int city = Integer.parseInt(st.nextToken());
                if (city == 1) {
                    union(i, j);
                }
            }
        }
    }

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

    private static int find(int x) {
        if (x == parent[x]) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    private static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a < b) {
            parent[b] = a;
        } else {
            parent[a] = b;
        }
    }
}

📄 해설

접근

• 서로소 집합 활용 문제.
• 도시들 간 연결 여부를 입력 받을 때 해당 위치 값이 1이면 union 연산을 수행한다.
• 이후 여행 계획 배열을 순회하면서 붙어있는 위치들의 부모노드가 다르면 NO, 순회가 문제 없이 종료되면 YES 를 출력한다.

과정

• 부모 테이블 parent 를 초기화한다.
• 도시 간 연결 정보를 입력 받는다. 이때, 1 을 입력 받을 경우 해당 위치 i, j 는 연결 된 도시이므로, union 연산을 수행한다.
• 이후 여행 경로를 입력 받고, 2번째 경로부터 find 연산을 통해 이전 경로와 연결되어 있는지를 확인하면서 여행이 가능한지 확인한다. (두 도시의 부모가 다르면 서로 연결이 되어있지 않은 것)