[BOJ] 16964 - DFS 스페셜 저지

https://www.acmicpc.net/problem/16964

BOJ - DFS 스페셜 저지

문제 유형: DFS/BFS

문제 난이도: Gold III

시간 제한: 2초

메모리 제한: 512MB

 

문제

BOJ에서 정답이 여러가지인 경우에는 스페셜 저지를 사용한다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식이다. 오늘은 스페셜 저지 코드를 하나 만들어보려고 한다.

정점의 개수가 N이고, 정점에 1부터 N까지 번호가 매겨져있는 양방향 그래프가 있을 때, DFS 알고리즘은 다음과 같은 형태로 이루어져 있다.

void dfs(int x) {
    if (check[x] == true) {
        return;
    }
    check[x] = true;
    // x를 방문
    for (int y : x와 인접한 정점) {
        if (check[y] == false) {
            dfs(y);
        }
    }
}

 

이 문제에서 시작 정점은 1이기 때문에 가장 처음에 호출하는 함수는 dfs(1)이다. DFS 방문 순서는 dfs함수에서 // x를 방문 이라고 적힌 곳에 도착한 정점 번호를 순서대로 나열한 것이다.

트리가 주어졌을 때, 올바른 DFS 방문 순서인지 구해보자.

 

입력

첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루어져 있으며, 1부터 N까지 자연수가 한 번씩 등장한다.

 

출력

입력으로 주어진 DFS 방문 순서가 올바른 순서면 1, 아니면 0을 출력한다.

 

풀이

이 문제에서 트리의 간선은 양방향이다.

즉, 인접리스트를 만들 때, 양방향 연결을 만들어줘야 한다.

그리고, 문제를 보면 알 수 있듯이, 시작이 1이 아니면 안 된다.

 

입력의 DFS 방문 순서를 큐로 받는다.

그 큐대로 따라가기 위한 iterative한 dfs를 위해, 스택을 만든다.

 

처음에, 큐의 맨 앞을 pop하여 스택에 push한다.

즉, root부터 넣는다.

 

이제, 큐에 내용이 있는동안 다음을 반복한다:

  큐에서 요소를 하나 pop한다.

  이 노드가 다음 행선지이다.

 

  스택은 그 노드로 가기 위해, graph[stk.top()]에서 다음 행선지가 나올때까지 스택에서 pop한다.

  만약 스택이 비어서 그 노드로 갈 수 없다면, 유효한 dfs가 아닌 것이다.

  다음 노드를 방문처리하고, 스택에 다음 노드를 push한다.

 

그렇게 큐를 무사히 순회했다면, 유효한 dfs가 맞다.

 

참고로 이 로직으로는, 어떤 형태의 dfs이던 감지할 수 있다.

preorder, inorder, postorder다 상관없다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int n;

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin >> n;
  vector<set<int>> graph(n + 1);
  int parent, child;
  for (int i = 0; i < n - 1; ++i) {
    cin >> parent >> child;
    graph[parent].insert(child);
    graph[child].insert(parent);
  }

  queue<int> q;
  int tmp;
  for (int i = 0; i < n; ++i) {
    cin >> tmp;
    q.push(tmp);
  }

  if (q.front() != 1) {
    cout << "0\n";
    return 0;
  }

  stack<int> stk;
  stk.push(q.front());
  q.pop();

  while (!q.empty()) {
    int next = q.front();
    q.pop();

    while (!stk.empty() &&
           graph[stk.top()].find(next) == graph[stk.top()].end()) {
      stk.pop();
    }
    if (stk.empty()) {
      cout << "0\n";
      return 0;
    }
    stk.push(next);
  }

  cout << "1\n";
  return 0;
}