[백준/BOJ] 16964번 DFS 스페셜 저지 (C++)

www.acmicpc.net/problem/16964

16964번: DFS 스페셜 저지

DFS 유형의 문제입니다. (다시 풀기)

입력값으로 받는 DFS의 진행 순서에 맞게끔 각각의 노드에 인접한 노드들을 내림차순으로 정렬하는 것이 포인트였던 문제였습니다. 

 

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

vector<int> graph[100001];
bool visit[100001];
vector<int> order(100001), answer;

int cmp(int a, int b) {
    return order[a] < order[b];
}

void DFS(int node) {
    answer.push_back(node);
    
    for(int i = 0; i < graph[node].size(); i++) {
        int next = graph[node][i];
        if(visit[next]) continue;
        visit[next] = true;
        DFS(next);
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<int> input(n);
    
    for(int i = 0; i < n - 1; i++) {
        int v1, v2;
        cin >> v1 >> v2;
        graph[v1].push_back(v2);
        graph[v2].push_back(v1);
    }
    
    for(int i = 0; i < n; i++) {
        cin >> input[i];
        order[input[i]] = i + 1; // 그래프 정렬을 위해 각 노드의 DFS 진행 순서 저장 
    }
    
    int start = input[0];
    if(start != 1) {
        cout << "0";
        return 0;
    }
    
    // 각 노드에 인접한 노드를 DFS 진행 순서에 맞게 내림차순 정렬
    for(int i = 1; i <= n; i++) {
        sort(graph[i].begin(), graph[i].end(), cmp);
    }
    
    visit[start] = true;
    DFS(start);
    
    if(answer == input) cout << "1";
    else cout << "0";
}