백준 1976: 여행 계획(Java)

도시 N개가 주어지고, 각 도시 간 연결 여부가 인접 행렬로 주어진다.
이후 M개의 도시가 주어졌을 때, 해당 도시들을 순서대로 여행할 수 있는지 판별하라.

• 연결된 도시는 자유롭게 이동 가능
• 단, 연결 여부는 직간접(경유)을 모두 포함함
• 핵심은 모든 도시가 하나의 네트워크(그룹)에 포함되어 있어야 한다는 것

---

🔍 알고리즘 설계

✅ 핵심 아이디어: Union-Find(Disjoint Set)

• 도시 간 연결 관계를 Union-Find로 관리
• 여행 경로에 등장하는 모든 도시가 같은 그룹(root)에 속해 있어야 YES
• 하나라도 다르면 NO

---

🔧 핵심 구현 로직

int cityCount = Integer.parseInt(br.readLine());
int planCount = Integer.parseInt(br.readLine());

parent = new int[cityCount + 1];
for (int i = 1; i <= cityCount; i++) parent[i] = i;

for (int i = 1; i <= cityCount; i++) {
    st = new StringTokenizer(br.readLine());
    for (int j = 1; j <= cityCount; j++) {
        int isConnected = Integer.parseInt(st.nextToken());
        if (isConnected == 1) union(i, j);
    }
}

• 도시 간 인접행렬을 통해 union 연산 수행
• 여행 계획 입력 후 모든 도시의 root가 동일한지 확인

---

💻 전체 코드

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));
        StringTokenizer st;

        int cityCount = Integer.parseInt(br.readLine());
        int planCount = Integer.parseInt(br.readLine());

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

        for (int i = 1; i <= cityCount; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= cityCount; j++) {
                int isConnected = Integer.parseInt(st.nextToken());
                if (isConnected == 1) {
                    union(i, j);
                }
            }
        }

        st = new StringTokenizer(br.readLine());
        int startRoot = find(Integer.parseInt(st.nextToken()));

        for (int i = 1; i < planCount; i++) {
            int currentCity = Integer.parseInt(st.nextToken());
            if (startRoot != find(currentCity)) {
                System.out.println("NO");
                return;
            }
        }

        System.out.println("YES");
    }

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

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

---

⏱ 시간 복잡도

• Union-Find 연산: 거의 O(1) (경로 압축)
• 도시 수 N, 여행 계획 길이 M
• 총 시간 복잡도: O(N² + Mα(N))

---

✅ 학습 정리

• Union-Find는 네트워크 연결성 판단 문제에서 매우 유용
• 연결된 도시만 union 처리 → 최종적으로 같은 그룹인지 판별
• 경로 압축과 루트 비교를 통해 빠른 연결성 검증 가능