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

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

16940번: BFS 스페셜 저지

이 문제는 지문을 너무 대충 읽고 넘어갔다가 몇 번 틀리고 말았다.

먼저 지문을 자세히 읽고 유의 사항을 짚어보자.

---

1. 이 문제에서 시작 정점은 1이다.

-> 입력 순서는 무조건 1부터 시작하지 않을 수 있다.

때문에 입력 순서의 첫 번째가 1이 아닐 경우 무조건 틀린 순서이다.

 

2. X와 연결되어있으면, 아직 방문하지 않은 정점 Y를 모두 큐에 넣는다 + 트리가 주어졌을 때

-> 이 해설 때문에 아래와 같은 트리 구조의 가능한 순서와 불가능한 순서는 다음과 같다.

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 (O)

1 -> 3 -> 2 -> 6 -> 7 -> 4 -> 5 (O)

1 -> 3 -> 2 -> 6 -> 5 -> 4 -> 7 (X)

---

위의 유의 사항들을 모두 이해했으면 문제 풀이는 그리 어렵지 않다. 문제에서 주어진대로 방문 여부를 따져가며 코드를 작성하면 되기 때문이다.

 

나는 방문 여부를 따질까 고민하다가 그냥 머릿속에서 떠오른 방식 그대로 구현해보았다.

 

문제 풀이는 다음과 같다.

1. 먼저 입력값들을 모두 저장해준다.

    int n, a, b;
    cin >> n;
    vector<vector<int>> v(n + 1, vector<int>());
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    vector<int> q(n);
    for (int i = 0; i < n; i++) cin >> q[i];

v는 양방향 그래프를 저장할 벡터이며, q는 올바른 순서인지 판단할 벡터이다.

 

2. 먼저 큐에 입력된 첫 번째 값이 1인지 판단한다. 1이 아닐 경우 곧 바로 0을 종료하고 출력하면 된다.

void fail() {
    cout << "0" << "\n";
    exit(0);
}
 
  ... // 아래는 int main()함수
 
    int idx = 0, pos, cnt;
    if (q[idx] != 1) fail();
    queue<int> temp;
    temp.push(1);
    idx++; // q 벡터의 현재 위치 증가

첫 번째 값이 1일 경우 올바른 순서의 판단을 진행해야 하므로, 큐를 하나 만들어 해당 큐에 1을 삽입한다.

또한 판단해야하는 순서가 저장된 q 벡터의 현재 판단할 위치값을 +1 해준다.

 

3. 아래는 BFS를 진행할 while문이다.

    while (!temp.empty()) {
        pos = temp.front();
        temp.pop(); // 1
        pos == 1 ? cnt = v[pos].size() : cnt =  v[pos].size() - 1; // 2
        while (cnt) { // 3
            auto now = find(v[pos].begin(), v[pos].end(), q[idx]); // 4
            if (now!=v[pos].end()) { // 5
                v[pos].erase(now);
                if (v[q[idx]].size() > 1) temp.push(q[idx]);
                cnt--;
                idx++;
            }
            else fail(); // 6
        }
    }

(1) temp 큐에 저장된 첫 번째 값을 변수 pos에 저장한다. 그리고 큐를 pop해준다.

(2) cnt함수는 현재 벡터에 연결된 값들을 저장할 횟수를 의미한다.

만약 pos가 1일 경우, 이는 root값이다. 때문에 더 이상의 부모는 존재 하지 않으므로, v[pos]의 사이즈가 그대로 cnt에 저장된다. 반대로 pos가 1이 아닐 경우, 무조건 부모 노드를 1개 가지고 있기 마련이다. 때문에 v[pos]의 사이즈 -1을 cnt에 저장해준다.

(3) cnt의 갯수가 0이 될때 까지, 즉, 모든 자식노드를 방문할때까지 while문이 진행된다.

(4) 현재 찾아야하는 q 벡터의 순서값이 q[idx]이다. 이 q[idx]가 v[pos]배열에 있을 경우, now는 해당 배열의 주소값을 가리키는 포인터이다.

(5) 만약 주소값이 존재할 경우, 보다 빠른 탐색을 위해 해당 값을 배열에서 제거해준다.

동시에 v[q[idx]]의 사이즈가 1보다 클경우, 이는 자식 노드를 가지고 있음을 뜻한다. 때문에 temp 큐에 저장해준다.

마지막으로 cnt의 갯수를 -1해주고 idx(찾아야하는 순서를 저장한 벡터의 현재 위치)의 값을 +1 해준다.

(6) 반대로 주소값이 존재하지 않을 경우, 곧 바로 fail()함수를 호출하고 종료한다.

 

4. 이 모든 과정을 끝내고 while(!temp.empty())를 빠져나올 경우, 1을 출력해주고 종료하면 된다.

 

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

void fail() {
    cout << "0" << "\n";
    exit(0);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, a, b;
    cin >> n;
    vector<vector<int>> v(n + 1, vector<int>());
    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    vector<int> q(n);
    for (int i = 0; i < n; i++) cin >> q[i];
    int idx = 0, pos, cnt;
    if (q[idx] != 1) fail();
    queue<int> temp;
    temp.push(1);
    idx++;
    while (!temp.empty()) {
        pos = temp.front();
        temp.pop();
        pos == 1 ? cnt = v[pos].size() : cnt =  v[pos].size() - 1;
        while (cnt) {
            auto now = find(v[pos].begin(), v[pos].end(), q[idx]);
            if (now!=v[pos].end()) {
                v[pos].erase(now);
                if (v[q[idx]].size() > 1) temp.push(q[idx]);
                cnt--;
                idx++;
            }
            else fail();
        }
    }
    cout << "1" << "\n";
    return 0;
}

 

코드의 동작시간이 너무 많이 소비되어서 여러가지 방법을 고안해봤지만, 모든 코드에서 공통적으로 find를 활용한 탓인지 시간초를 크게 줄일 수는 없었다. 맞은 사람들 중 160ms 이하로 푸신 분들도 계신데, 그 사람들은 어떤 코드를 작성한건지 궁금하다.