[백준] 1976번. 여행 가자(JAVA)

문제

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

---

풀이(25분)

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

public class Main {

    static int[] parent;

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

        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++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                if (Integer.parseInt(st.nextToken()) == 1) { // 연결되어 있다면
                    union(i, j); // 두 도시를 같은 집합으로 묶음
                }
            }
        }

        // 여행 계획 입력
        st = new StringTokenizer(br.readLine());
        int firstCity = find(Integer.parseInt(st.nextToken()) - 1); // 첫 번째 도시의 대표
        boolean canTravel = true;

        for (int i = 1; i < m; i++) {
            int nextCity = Integer.parseInt(st.nextToken()) - 1;
            if (find(nextCity) != firstCity) { // 다른 대표를 가진 도시 발견
                canTravel = false;
                break;
            }
        }

        System.out.println(canTravel ? "YES" : "NO");
    }

    // Find: 대표 노드를 찾는 함수 (경로 압축)
    public static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 경로 압축
        }
        return parent[x];
    }

    // Union: 두 집합을 합치는 함수
    public static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            parent[rootB] = rootA; // 두 집합을 합침
        }
    }
}

 

여행의 경로가 중요한 것이 아닌 갈 수 있는지! 만 중요한 것이다. 즉, 동일한 부모를 바라보고 있다면 경로가 가능하다! 라고 결론을 내렸고, 유니온 파인드 알고리즘을 도입하여 문제를 해결할 수 있었다.

 

1. 모두 자기 자신의 인덱스를 바라보고 있는다.

2. 경로가 있다면 인덱스를 통일한다.(0-1이 연결된 길이 있다면 둘 다 인덱스를 0으로 맞추는 것이다.)

3. 이 과정을 반복한다.

 

4. 최종적으로 가고자 하는 경로의 인덱스를 보면 된다!