[백준/C++] 여행 가자 (No. 1976)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 특정 경로가 서로 연결된 상태인지 구하는 문제다.

왜냐하면 여러 경로가 주어지고, 그 경로를 따라 이동할 수 있는지 묻는 문제기 때문이다.

 

그래서 Union Find로 분류된 문제지만, 단순한 BFS로 풀 수 있다.

 

간단히 BFS로 푸는 방법을 설명하자면, 주어진 경로에 있는 위치에서 탐색을 시작한다.

그리고 방문한 노드들을 기록할 배열 visited를 만든 뒤 방문한 위치는 true로 바꿔준다.

 

이제 주어진 경로를 탐색하며 한번이라도 방문하지 않은 노드가 있다면, NO를 출력하면 된다.

 

즉, 문제를 요약하면 특정 경로에 있는 모든 노드는 연결되어 있어야 하므로, BFS로 방문표시를 하며 탐색을 하면 연결된 노드들은 전부 True로 바뀐다.

 

그러므로 연결되지 않은 노드는 False상태이므로, 경로에 False상태인 노드가 하나라도 있으면, 갈 수 없다는 의미다.

 

처음 문제를 푼 방법은 BFS로 탐색을 하고 1차원 배열에 원소들이 속한 집합의 대표 원소를 저장하는 방법으로 풀었다.

 

그리고 대표원소가 다른 경로가 하나라도 있으면, 이어진 경로가 아니므로 No를 출력하도록 했다.

하지만 잘 생각해보니 굳이 대표원소를 표시하지 않아도 되겠다는 생각에 BFS로 한번 더 풀게 됐다.

 

 

​

[아이디어 정리]

1. 2차원 배열에 방문할 수 있는 노드들을 기록한다.
2. 모든 경로에 있는 노드들이 연결되어 있어야 하므로, 첫 노드를 기준으로 BFS로 탐색하며 방문한 적이 있는지 표시한다.
3. 경로에 있는 원소들을 방문한 적이 없다면, 그 노드는 연결되지 않았다는 뜻이므로 NO를 출력한다.
4. 모든 경로가 방문한 적이 있다면, True를 출력한다.

 

 

 

Code (BFS)

 

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<bool> visited(n + 1, false);
    vector<vector<int>>graph(n);
    int jj = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> jj;
            if (jj == 1)
            {
                graph[i].push_back(j);
            }
        }
    }


    cin >> jj;
    visited[jj - 1] = true;
    queue<int> q;
    q.push(jj - 1);
    int tmp;
    while (!q.empty()) {
        tmp = q.front();
        q.pop();
        for (int i = 0; i < graph[tmp].size(); i++) {
            if (!visited[graph[tmp][i]]) {
                visited[graph[tmp][i]] = true;
                q.push(graph[tmp][i]);
            }
        }
    }
    for (int i = 1; i < m; i++) {
        cin >> jj;
        if (!visited[jj - 1]) {
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";

    return 0;
}

 

---

 

Code (집합의 대표원소 기록)

 

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> par(n, -1);
    vector<vector<int>>graph(n);
    int jj=0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> jj;
            if (jj == 1)
            {
                graph[i].push_back(j);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (par[i] == -1) {
            par[i] = i;
            queue<int> q;
            q.push(i);
            while (!q.empty()) {
                int tmp = q.front();
                q.pop();
                for (int j = 0; j < graph[tmp].size(); j++) {
                    if (par[graph[tmp][j]] == -1) {
                        par[graph[tmp][j]] = i;
                        q.push(graph[tmp][j]);
                    }
                }
            }
        }
    }
    cin >> jj;
    int cmpU = par[jj-1];
    for (int i = 1; i < m; i++) {
        cin >> jj;
        if (par[jj-1] != cmpU) {
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";

    return 0;
}

 

---

문제의 유형을 보면 괜히 그 유형의 방식대로 따라가는 것 같다.

자꾸 유형을 보고 따라하게 되면, 새 문제가 나타났을 때 머리가 굳어 해결력이 떨어지게 될 것 같다는 생각이 든다.

그래서 항상 다른 풀이가 없이 이 풀이가 최적일까? 고민하면서 더 좋은 풀이가 있는지 생각하는데 이 과정이 생각보다 재밌다.