[백준, C++] 1976 - 여행 가자

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

1976번: 여행 가자

 

문제 분석

그래프가 있고, 이 그래프에서 방문하고자 하는 정점의 번호가 주어진다. 이 때, 이 정점들을 모두 경유할 수 있는 경로가 있는지 탐색하면 된다.

사실 문제를 보고 이 문제는 BFS로도 충분히 풀 수 있을 것 같다는 생각이 들었지만, disjoint-set, 즉 Union-Find를 활용해 풀 수 있을 것이라는 생각이 들었다. 그래서 Union-Find로 한 번 풀고, BFS로 한 번 더 풀었다.

 

코드

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int n, m;
int arr[201][201];
set<int> cities;
vector<int> vec[201];
int parent[201];
bool result = true;

int findParent(int v) {
    if (v == parent[v]) {
        return parent[v];
    }
    return parent[v] = findParent(parent[v]);
}

void unionParent(int v1, int v2) {
    int v1Root = findParent(v1);
    int v2Root = findParent(v2);

    if (v1Root < v2Root) {
        parent[v2Root] = v1Root;
    } else {
        parent[v1Root] = v2Root;
    }
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }

    for (int i = 0; i < m; i++) {
        int city;
        cin >> city;
        cities.insert(city);
    }

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (arr[i][j] == 1 && parent[i] != parent[j]) {
                unionParent(i, j);
            }
        }
    }

    int p = parent[*(cities.begin())];
    for (auto city : cities) {
        if (p != parent[city]) {
            result = false;
        }
    }

    cout << (result ? "YES\n" : "NO\n");
    return 0;
}

 

코드 설명

Union-Find는 Union 메서드와 Find 메서드를 사용한다.

Union 메서드는 두 정점을 하나의 집합으로 합쳐주는 기능을 수행한다. Find 메서드는 한 정점의 조상 정점의 번호를 찾아주는 기능을 수행한다.

 

여행 경로 사이사이에 다른 정점이 껴도 상관없다고 했기 때문에, 나는 여행갈 목적지 도시 정점을 set에 담아 관리했다. A-B-C-B-A 라는 여행 경로가 주어졌을 때, A에서 C로 가는 경로가 있다면 (문제에서 양방향 간선이라고 했으므로) C에서 A로 가는 경로도 당연히 있을 것이고, 이 말인즉슨 A에서 C로 가는 경로가 있다면 그 뒤 반복되는 건 ... 굳이 구하지 않아도 되기 때문이다.

 

오랜만에 Union-Find를 사용해봤다. 메서드 내부를 까먹어서 조금 오래 걸렸다.