[백준] 16940번 : BFS 스페셜 저지

문제

 

---

풀이

 

이런 그래프가 있다고 하자. 이 그래프를 탐색할 시 선택의 순간이 2번 있다.

바로 1번 정점과 2번 정점에서이다.

 

1번 정점에선 2번 또는 3번 정점으로 갈 수 있다. 2->3의 순서로 큐에 넣어도 되고 3->2의 순서로 큐에 넣어도 된다.

2번 정점에선 마찬가지로 4->5 또는 5->4의 순서로 큐에 넣을 수 있다.

 

이 순서는 순전히 처음에 그래프의 연결된 정점을 어떤 순서로 저장했느냐에 따라 달라진다.

1->2, 3으로 저장했다면 2->3의 순서로 큐에 들어갈 것이고

1->3, 2로 저장했다면 3->2의 순서로 큐에 들어갈 것이다.

 

입력된 방문 순서에 따라 정점의 저장 순서를 바꿀 것이다.

먼저 인접 정점의 정보를 이렇게 저장했었다고 가정하자.

 

1->2, 3

2->1, 4, 5

3->1, 6

4->2

5->2

6->3

 

그리고 입력된 방문 순서는 1 3 2 4 5 6이라고 하자. 이 입력 순서를 인덱스와 함께 적으면

0 1 2 3 4 5

1 3 2 4 5 6

이렇게 된다.

 

입력된 방문 순서를 살펴보면

1번 정점에선 3->2의 순서로 방문 정점을 선택하고 2번 정점에선 4->5로 선택했음을 알 수 있다.

 

3의 인덱스는 2보다 작고, 4의 인덱스는 5보다 작다.

그니까 이 인덱스를 기준으로 그래프의 정보를 오름차순으로 바꾸면 된다.

 

1->3, 2

2->1, 4, 5

3->1, 6

4->2

5->2

6->3

 

이 상태에서 bfs를 실행했을 때 입력된 방문 순서와 일치한다면 올바른 방문 순서인 것이다.

---

소스코드

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> graph;
vector<int> route, visited, idx, result;

bool cmp(const int &i1, const int &i2) {
    if (idx[i1] < idx[i2])
        return true;
    else
        return false;
}

void bfs(int start) { //bfs 실행하며 결과를 result 벡터에 담기
    queue<int> q;

    visited[start] = 1;
    q.push(start);
    result.push_back(start);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = 0; i < graph[cur].size(); i++) {
            if (!visited[graph[cur][i]]) {
                visited[graph[cur][i]] = 1;
                q.push(graph[cur][i]);
                result.push_back(graph[cur][i]);
            }
        }
    }
}

bool isBFS() { //result와 route 비교
    for (int i = 0; i < route.size(); i++) {
        if (route[i] != result[i])
            return false;
    }
    return true;
}

int main() {
    int N, first, second;

    cin >> N;
    graph.assign(N + 1, vector<int>(0));
    visited.assign(N + 1, 0);
    idx.assign(N + 1, 0);
    route.assign(N, 0);
    for (int i = 1; i < N; i++) {
        cin >> first >> second;
        graph[first].push_back(second);
        graph[second].push_back(first);
    }
    for (int i = 0; i < N; i++) { //각 정점의 인덱스
        cin >> route[i];
        idx[route[i]] = i;
    }

    for (int i = 1; i <= N; i++) //idx 기준 오름차순 정렬
        sort(graph[i].begin(), graph[i].end(), cmp);

    bfs(1);
    cout << isBFS();
}

전체 소스코드다.

 

    for (int i = 0; i < N; i++) { //각 정점의 인덱스
        cin >> route[i];
        idx[route[i]] = i;
    }

경로를 입력받으면서 각 정점의 인덱스도 저장한다.

 

bool cmp(const int &i1, const int &i2) {
    if (idx[i1] < idx[i2])
        return true;
    else
        return false;
}
...
    for (int i = 1; i <= N; i++) //idx 기준 오름차순 정렬
        sort(graph[i].begin(), graph[i].end(), cmp);

그리고 그 인덱스를 기준으로 오름차순 정렬을 한다.

 

void bfs(int start) { //bfs 실행하며 결과를 result 벡터에 담기
    queue<int> q;

    visited[start] = 1;
    q.push(start);
    result.push_back(start);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = 0; i < graph[cur].size(); i++) {
            if (!visited[graph[cur][i]]) {
                visited[graph[cur][i]] = 1;
                q.push(graph[cur][i]);
                result.push_back(graph[cur][i]);
            }
        }
    }
}

시작 정점 1에 대해 bfs를 하며 그 결과를 result 벡터에 담는다.

 

bool isBFS() { //result와 route 비교
    for (int i = 0; i < route.size(); i++) {
        if (route[i] != result[i])
            return false;
    }
    return true;
}

입력 경로를 담은 route 벡터와 result 벡터가 일치하면 옳은 bfs 경로인 것이다.