[C++][백준 16964] DFS 스페셜 저지

문제

접근 방법

스택과 DFS의 관계를 생각하여서 풀 수 있다.

스택에 최근에 방문한 정점을 저장해 주면 된다. 인근에 방문 순서와 일치하는 정점이 존재하면 올바른 순서인 것이고 없다면 부모 정점으로 이동하여 다시 확인해 본다.

이 과정을 반복하여 1번 정점에서도 불가능하다고 판단되면 순서가 잘못된 것이다.

코드

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<vector<int>> graph;
vector<int> order;
int N;
void input()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    graph = vector<vector<int>>(N + 1, vector<int>());
    order = vector<int>(N);
    for (int i = 1, a, b; i < N; ++i)
    {
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for (int &i : order)
    {
        cin >> i;
    }
}
bool solve()
{
    stack<int> s;
    s.push(1);
    for (int i = 1; i < N; ++i)
    {
        while (!s.empty()) // 스택이 비어있지 않다면
        {
            bool isFind = false;
            for (int j : graph[s.top()]) // 인접한 정점
            {
                if (order[i] == j) // 순서와 정점이 일치하면 가능한 것
                {
                    isFind = true;
                    break;
                }
            }
            if (isFind) // 가능하다면 스택에 집어넣기
            {
                s.push(order[i]);
                break;
            }
            else // 불가능하면 현재 정점의 부모로 돌아가기
            {
                s.pop();
            }
        }
        if (s.empty()) // 1번 정점에서도 불가능한 것
        {
            return false;
        }
    }
    return true;
}
int main()
{
    input();
    cout << solve();
    return 0;
}

풀이

DFS는 끝까지 파고드는 것임을 생각해 주면 된다.

만약 인근 정점과 순서가 일치하지 않다면 지금 정점은 더 이상 갈 곳이 없다거나 잘못된 정점이란 것이다. 전자의 가능성을 위해 부모 정점으로 돌아가 주면 되는 것이다.