BOJ (Java) 1976번: 여행 가자

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

---

풀이

이전에는 프림 알고리즘을 사용했고, 이번에도 해당 알고리즘을 떠올렸으나 분리-집합으로 풀었다.

주어진 경로로 가는 도중에 다른 노드에 들렀다 갈 수 있어 실질적으로는 모든 노드가 같은 집합 내에 위치해 있는지를 확인하면 된다.

이 때 주어진 연결 정보가 1-2, 2-1로 양방향으로 주어지기에, 각 노드들이 같은 노드에 속해있지 않은 경우에만 합쳐줘야 한다.

 

 

BOJ (C/C++) 1976번: 여행 가자

 

---

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

    private static void union(int a, int b) {
        parents[b] = a;
    }

    private static int find(int a) {
        if (a == parents[a])
            return a;
        return parents[a] = find(parents[a]);
    }

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

        String input = bf.readLine();
        N = Integer.parseInt(input);
        input = bf.readLine();
        M = Integer.parseInt(input);

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

        for (int i = 0; i < N; i++) {
            String[] tmp = bf.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                int isConnected = Integer.parseInt(tmp[j]);
                if (isConnected == 1 && find(i) != find(j))
                    union(find(i), find(j));
            }
        }

        String[] paths = bf.readLine().split(" ");
        for (int i = 0; i < M - 1; i++) {
            int a = Integer.parseInt(paths[i]) - 1;
            int b = Integer.parseInt(paths[i + 1]) - 1;
            if (find(a) != find(b)) {
                System.out.println("NO");
                return;
            }
        }
        System.out.println("YES");
    }
}