[DFS] 백준 16964 DFS 스폐셜 저지(C++)

 

 

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

 

 

[BFS] 백준 16940 BFS 스폐셜 저지(C++)

[BFS] 백준 16940 BFS 스폐셜 저지(C++)

 

사실 BFS 풀고 다음날에 푼 문제인데, 막혀가지고 이제서야 올린다

 

문제 자체는 BFS와 동일하게 접근하면 될 것 같다.

 

BFS에서 문제를 풀 때 어떻게 풀었냐면

 

시간 감소를 위해

 

"먼저 입력된 배열 순으로 vector를 정렬"

 

앞선 BFS 문제 풀이에 다 나와있으니 해당 내용을 꼭 읽길 바란다.

 

만약 이렇게 입력된 배열순으로 vector를 정렬 했다면 

"DFS에서 1을 기준으로 그 다음 깊이로 갈때 당연히, 배열 순서대로 나올 것이다"

 

그래서 backtraking을 안하게 visited == true만 해주고

 

각 위치에 해당하는 값을 저장후에

마지막에 비교해서 아니면 0 맞으면 1을 출력하면 된다.

 

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

bool visited[100001];

using namespace std;

vector<int> v[100001];

int arr[100001];

int pos[100001];

void bfs(int temp);

void dfs(int temp, int depth);

int test[100001];

int count_1 = 1;

int n;

bool compare(int &a, int &b)

{

    return pos[a] < pos[b];

}

int main()

{

    cin >> n;

    for (int i = 0; i < n - 1; i++)

    {

        int a, b;

        cin >> a >> b;

        v[a].push_back(b);

        v[b].push_back(a);

    }

    for (int i = 0; i < n; i++)

    {

        cin >> arr[i];

        pos[arr[i]] = i;

    }

    for (int i = 1; i <= n; i++)

    {

        sort(v[i].begin(), v[i].end(), compare);

    }

    if (arr[0] != 1)

    {

        cout << 0 << "\n";

        return 0;

    }

    visited[1] = true;

    test[0] = 1;

    dfs(1, 0);

    for (int i = 0; i < n; i++)

    {

        if (arr[i] != test[i])

        {

            cout << 0 << "\n";

            return 0;

        }

    }

    cout << 1 << "\n";

    return 0;

}

void dfs(int temp, int depth)

{

    for (int i = 0; i < v[temp].size(); i++)

    {

        int x = v[temp][i];

        if (!visited[x])

        {

            visited[x] = true;

            test[count_1] = x;

            count_1++;

            dfs(x, depth + 1);

        }

    }

}

 

bfs dfs spcial judge문제 모두 입력된 수열의 정렬을 생각해낸다면 문제 풀이는 정말 쉬울 것이다.