BOJ_1976 : 여행 가자

👉 문제링크

1976번: 여행 가자

---

 

---

🔸 문제 분석 🔸

• N개의 도시 중 M개의 도시를 여행하고자 한다.
• 경로가 있어서 여행이 가능하면 YES, 불가능하면 NO를 출력한다.

🔸 문제 풀이 🔸

• 여행 하고자 하는 M개의 도시 간에 경로가 있는지 파악하는 쉬운 방법은 같은 집합에 있는지 확인하는 것이다.
  • 분리 집합(Disjoint Set)으로 N개의 도시들의 집합을 나눈다.
  • 여행 계획상의 도시들이 같은 집합에 있으면 경로가 존재한다는 뜻이다.
  • 분리 집합이 아니라 BFS나 DFS로 Brute Force 알고리즘 탐색을 진행했다면, N이 200이고 M이 1000 이면서 1자형 그래프이고 끝에서 끝을 오고간다면 200^1000이라는 말도 안되는 시간 복잡도가 나온다.
  • 분리 집합의 시간 복잡도는 O(logN) 이므로 간단히 해결된다.
• 경로 유무가 N * N 인접 행렬로 주어지는데, 경로가 있다는 1 입력 시 union 연산을 수행한다.
• 마지막 M개의 여행 경로가 같은 집합에 있는지 find 연산을 수행한다.

🔸 코드 🔸

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

public class Main {
    private static int[] parent;

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

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

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

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

        st = new StringTokenizer(br.readLine());
        int set_parent = find(Integer.parseInt(st.nextToken()));
        String answer = "YES";

        for (int i = 1; i < M; i++) {
            if (set_parent != find(Integer.parseInt(st.nextToken()))) {
                answer = "NO";
                break;
            }
        }

        bw.write(answer);
        bw.flush();
    }

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

    private static boolean union(int a, int b) {
        int ap = find(a);
        int bp = find(b);
        if (ap != bp) {
            parent[ap] = bp;
            return true;
        }
        return false;
    }
}

🔸 코드 해석 🔸

• 분리 집합을 위해 union(), find() 메서드를 사용했는데, union() 메서드의 반환값은 사용되지 않으므로 boolean이 아니라 void 가 되어도 상관 없다.
• 분리 집합을 모두 수행한 후, 여행 경로 첫 번째 도시의 부모 노드 번호를 확인한 뒤, 다음 여행 경로 도시들의 부모 노드 번호와 같은지 확인한다.
  • 모두 같으면 YES, 하나라도 다르면 NO를 출력한다.

---

🔸 end 🔸

•  분리 집합을 알고리즘으로 선택하면 쉽게 풀 수 있는 문제였다.