알고리즘 :: 이것이 코딩 테스트다 :: 그래프 이론 문제 :: Q41 :: 여행 계획

문제

임의의 두 여행지 사이에는 양방향 도로가 있다. 여행계획은 여행지의 수 N과 여행 계획에 속한 도시의 수 M으로 이뤄진다. 한울이는 하나의 여행 계획을 세운 뒤에 이 여행 계획이 가능한지의 여부를 판별하는 프로그램을 작성하시오. (1 ≤ N, M ≤ 500)

문제접근

• 최소 거리를 구하려는 cost 관련 문제가 아니라는 점에 주목하자. 어떤 경로로 이동하던지 상관없이 여행계획 순서대로 이동만 가능하면 된다. 즉, 임의의 두 여행계획 상 목적지 사이에 x개의 중간 목적지가 있어도 상관없다. 도달만 하면 된다.
• 그러므로 이 문제는 임의의 두 목적지 A와 B가 같은 그래프 상에 존재하는지를 묻는 DFS 또는 서로소 집합 유형 문제다.
• 서로소 집합으로 이 문제를 풀어보자.

과정

1. N개의 도시가 있으므로 1부터 N까지의 모든 도시가 서로 다른 그룹에 속하도록 표시한다.

   1	2	3	4	5	6	...	N
   1	2	3	4	5	6	...	N

2. 임의의 두 목적지 A와 B를 잇는 간선이 주어진다면 서로소 집합의 union & find 연산을 수행한다.

3. 모든 간선에 대해 서로소 집합 연산을 수행하면 다음과 같은 형태의 결과가 나온다.

   1	2	3	4	5	6	...	N
   1	1	1	2	1	2	...	1

4. 위 표를 근거로, 1, 2, 3, 5, ... , N 번 도시는 서로 같은 그래프상에 놓인 정점이지만, 4, 6번은 다른 그래프에 놓인 정점이라는 것을 알 수 있다. 따라서 서로 간선이 이어져 있지 않으므로, 만일 여행계획에서 두 그래프에 속한 정점이 동시에 존재 (e.g. 1, 2, 4, 5) 한다면 해당 여행계획은 가능하지 않다고 판단할 수 있다.

코드

#include <iostream>
using namespace std;

static int N, M, rootInfo[501];

int findOperation(int x) {
    if (rootInfo[x] != x) return findOperation(rootInfo[x]);
    return rootInfo[x];
}
void unionOperation (int lhs, int rhs) {
    lhs = findOperation(lhs), rhs = findOperation(rhs);
    (lhs < rhs) ? (rootInfo[rhs] = lhs) : (rootInfo[lhs] = rhs);
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N >> M;
    // [과정1]: rootInfo 배열을 초기화: N개의 그룹으로 나눈다.
    for (int i = 1; i <= N; ++i) rootInfo[i] = i;
    // [과정2]: 간선을 입력받아 union 연산한다.
    for (int startV = 1; startV <= N; ++startV) {
        for (int endV = 1; endV <= N; ++endV) {
            int input;  cin >> input;
            if (input) unionOperation(startV, endV);
        }
    }
    // [과정3]: 여행 경로의 도시들이 같은 그룹내에 있지 않으면 false.
    bool flag = true;
    int temp;   cin >> temp;
    temp = findOperation(temp);
    for (int i = 1; i < M; ++i) {
        int planCityNum; cin >> planCityNum;
        if (temp != findOperation(planCityNum)) flag = false;
    }
    if (flag) cout << "YES\n";
    else cout << "NO\n";
}

결과

5 4
0 1 0 1 1
1 0 1 1 0 
0 1 0 0 0
1 1 0 0 0 
1 0 0 0 0
2 3 5 4
YES

5 4
0 1 0 1 0
1 0 1 1 0 
0 1 0 0 0
1 1 0 0 0 
0 0 0 0 0
2 3 5 4
NO