백준 16940번 BFS 스페셜 저지 (C++) - 2

문제 링크 : www.acmicpc.net/problem/16940

16940번: BFS 스페셜 저지

이 문제를 이전에 풀었을 때, 머릿속에서 나온 생각대로 무작정 풀었섰다.

백준 16940번 BFS 스페셜 저지 (C++) - 1

문제는 맞췄지만 시간이 1112ms가 소비되어 효율적인 로직이 아니라고 판단되었고, 고민하며 다시 한 번 풀어봤다.

몇 번의 시도 끝에 시간을 1/20 가까이 낮추어 효율적인 로직을 완성하게 되었다.

 

문제 풀이는 다음과 같다. 

1. 먼저 필요한 변수들을 전역변수로 설정한다. 동적할당을 해도 되지만 1차원 배열의 최대 사이즈 100,000가 그리 많은 메모리와 시간을 잡아먹지 않으므로, 배열로 설정해도 무방하다.

int n, a, b, pos;
vector<int> v[100001]; // 노드의 간선들을 저장할 벡터
queue<int> order; // 순서가 맞는지 판단할 큐
int bfs_order[100001]; // 노드의 간선들의 우선순위를 정렬할 벡터

2. 입력값들을 모두 저장한다. 이때 bfs_order에 저장되는 값을 한 번 자세히 봐보자.

    cin >> n;
    for (int i = 0; i < n - 1; i++) { // 간선 저장
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a); 
    }
    for (int i = 1; i <= n; i++) { // 순서 큐 저장 
        cin >> a;
        order.push(a);
        bfs_order[a] = i; // 간선의 우선순위 저장
    }

 

 

 

3. bfs_order에 저장된 값의 순서에 따라 양방향 간선들이 저장된 벡터 v를 정렬해준다.

bool comp(const int& a, const int& b) {
    return bfs_order[a] < bfs_order[b];
}

...

// int main() 내부
    for (int i = 1; i <= n; i++) {
        sort(v[i].begin(), v[i].end(), comp);
    }

위의 정렬을 통해 우선순위를 기준으로 정렬된다.

아래 그림에서 붉은색으로 표기된 숫자는 bfs_order에서 해당 숫자의 우선순위를 나타낸다.

 

Before

 

 

 

After

 

4. 순서를 판단할 큐의 첫번째가 1이 아닐 경우 곧 바로 0을 출력하고 종료한다.

반대의 경우, 새로 큐 temp를 하나 만들어 해당 큐에 1을 넣어주고, 큐가 empty될때까지 while문을 종료한다.

    if (order.front() != 1) {
        cout << "0" << "\n";
        exit(0);
    }
    else {
        queue<int> temp;
        temp.push(1);
        order.pop();
        while (!temp.empty()) {
            pos = temp.front();
            temp.pop();
            for (auto i : v[pos]) {
                if (i == order.front()) {
                    temp.push(order.front());
                    order.pop();
                }
                else;
            }
        }
    }

만약 v[큐의 첫 번째 값][i]의 값이 순서 큐의 첫 번째 값과 다를 경우, 더 이상의 작업 없이 while문을 종료한다.

 

5. 최종적으로 순서 큐가 비어있을 경우 1을, 그렇지 않을 경우 0을 출력한다.

    if (order.empty()) cout << "1" << "\n";
    else cout << "0" << "\n";

 

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

int n, a, b, pos;
vector<int> v[100001];
queue<int> order;
int bfs_order[100001];

bool comp(const int& a, const int& b) {
    return bfs_order[a] < bfs_order[b];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for (int i = 1; i <= n; i++) {
        cin >> a;
        order.push(a);
        bfs_order[a] = i;
    }
    for (int i = 1; i <= n; i++) {
        sort(v[i].begin(), v[i].end(), comp);
    }
    if (order.front() != 1) {
        cout << "0" << "\n";
        exit(0);
    }
    else {
        queue<int> temp;
        temp.push(1);
        order.pop();
        while (!temp.empty()) {
            pos = temp.front();
            temp.pop();
            for (auto i : v[pos]) {
                if (i == order.front()) {
                    temp.push(order.front());
                    order.pop();
                }
                else;
            }
        }
    }
    if (order.empty()) cout << "1" << "\n";
    else cout << "0" << "\n";
    return 0;
}

 

 

▲정렬을 구현한 코드의 채점결과

 

 

 

▲ find를 활용하여 일일이 대조작업을 진행했던 예전 코드