b1976. 여행가자

 

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

 

 

 

 

✈ 자바로 푸는 여행가자 문제 풀이

📌 문제 개요

 

여행 계획에 따라 여러 도시를 순서대로 방문할 수 있는지 판단하는 문제입니다.

도시 간의 연결 여부가 주어지며, 여행 경로에 포함된 모든 도시가 **같은 네트워크(연결된 그룹)**에 있어야 합니다.

 

• 1은 도시간 연결을 의미하고 0은 연결이 없음을 의미합니다.
• Union-Find(Disjoint Set)를 활용하여 각 도시가 같은 그룹에 속하는지 판단하면 됩니다.

 

---

 

💡 예제 입력

3
3
0 1 0
1 0 1
0 1 0
1 2 3

출력:

YES

 

 

---

 

🧠 알고리즘 접근 방식

 

1. Union-Find 자료구조를 사용해 도시 간 연결 정보를 하나의 집합으로 병합합니다.
2. 여행 계획에 포함된 도시들이 **모두 같은 집합(루트가 같음)**에 있는지 확인합니다.
3. 하나라도 다른 집합이면 NO, 모두 같으면 YES를 출력합니다.

 

---

 

🧾 코드 해설

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

public class Main {
    static int n, m;
    static int[] p;

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

        n = toInteger(br.readLine());  // 도시 수
        m = toInteger(br.readLine());  // 여행 계획 도시 수
        p = new int[n + 1];

        for (int i = 1; i <= n; i++) p[i] = i;

        // 연결 행렬 입력받아 union 처리
        for (int i = 1; i <= n; i++) {
            String[] str = br.readLine().split(" ");
            for (int j = 1; j <= n; j++) {
                if (toInteger(str[j - 1]) == 1) {
                    union(i, j);
                }
            }
        }

        // 여행 계획 확인
        String[] s = br.readLine().split(" ");
        boolean impossible = false;
        for (int i = 1; i < m; i++) {
            if (find(toInteger(s[i - 1])) != find(toInteger(s[i]))) {
                impossible = true;
                break;
            }
        }

        sb.append(impossible ? "NO" : "YES");
        System.out.println(sb);
    }

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

    private static void union(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa != pb) p[pa] = pb;
    }

    private static int toInteger(String s) {
        return Integer.parseInt(s);
    }
}

 

 

---

 

✅ 핵심 포인트 정리

 

• **Union-Find(서로소 집합)**을 사용해 연결된 도시들을 하나의 집합으로 묶습니다.
• 여행 계획에 포함된 모든 도시가 같은 집합(같은 대표 도시)을 가진다면 이동이 가능하다고 판단합니다.
• 연결 여부를 나타내는 인접 행렬을 그대로 순회하며 union(i, j)를 수행합니다.

 

---

 

🌿 결론: 네트워크의 일원인가?

 

이 문제는 그래프 연결성을 Union-Find로 확인하는 전형적인 문제입니다.

크게 복잡한 구현 없이, 도시들이 하나의 연결된 집합에 있는지만 확인하면 되기에 로직은 단순하지만 핵심적인 사고가 요구됩니다.

 

“같은 네트워크에 있는가?” 라는 질문을 find()를 통한 대표 비교로 해결할 수 있다는 것이 이 문제의 핵심입니다.