백준 16964번 DFS 스페셜 저지 (C++)

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

16964번: DFS 스페셜 저지

이 문제는 백준 16940번 BFS 스페셜 저지 - 2에서 활용한 기법으로 풀 수 있다.

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

 

문제 풀이는 다음과 같다. 

 

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

int n, a, b;
vector<int> v[100001]; // 노드의 간선들을 저장할 벡터
bool ch[100001]; // 방문 여부 판단
int order[100001]; // 방문 순서의 우선순위를 정할 배열
vector<int> dfs_order; // dfs 통해 방문한 노드를 저장할 벡터 

 

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

    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    vector<int> temp(n + 1); // 올바른 순서인지 판단할 배열
    for (int i = 1; i <= n; i++) {
        cin >> temp[i];
        order[temp[i]] = i;
    }

 

 

 

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

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

...

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

 

5. dfs를 진행한기 이전에 dfs_order에 먼저 0을 삽입한다. 이는 편의상 숫자 1부터 진행을 하기 때문이다.

    dfs_order.push_back(0);
    if (temp[1] == 1) dfs(1);

방문해야할 첫번째 값이 1인 경우에만 dfs(1)을 진행한다.

void dfs(int pos) {
    if (ch[pos]) return;
    ch[pos] = true;
    dfs_order.push_back(pos);
    for (auto i : v[pos]) {
        if (!ch[i]) dfs(i);
    }
}

dfs 함수를 통해서 방문한 위치가 올바른 순서일 경우에만 dfs_order 벡터에 값을 저장해준다.

이때 방문한 위치를 bool문으로 방문표기해주는 것을 잊지말자.

 

6. dfs 함수를 종료하고, 만약 dfs_order벡터가 temp벡터(올바른 순서인지 판단할 벡터)와 동일한 경우에만 1을 출력한다. 그렇지 않을 경우엔 0을 출력한다.

    if (dfs_order == temp) cout << "1" << "\n";
    else cout << "0" << "\n";

 

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

int n, a, b;
vector<int> v[100001];
bool ch[100001];
int order[100001];
vector<int> dfs_order;

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

void dfs(int pos) {
    if (ch[pos]) return;
    ch[pos] = true;
    dfs_order.push_back(pos);
    for (auto i : v[pos]) {
        if (!ch[i]) dfs(i);
    }
}

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);
    }
    vector<int> temp(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> temp[i];
        order[temp[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
        sort(v[i].begin(), v[i].end(), comp);
    }
    dfs_order.push_back(0);
    if (temp[1] == 1) dfs(1);
    if (dfs_order == temp) cout << "1" << "\n";
    else cout << "0" << "\n";
    return 0;
}