백준 16940 BFS 스페셜 저지

작성일 | In |

Problem : BFS 스페셜 저지

유형 : BFS, 그래프

해결 전략

  • 순서가 올바르지 않다는것은, 접근해서는 안되는 차례에 방문한다는것이다.
  • 다음에 접근 할 수 있는 노드들을 목록에 저장하고, 다음에 접근하려는 것이 목록에 있는지 확인한다.

잘못된 접근 방법

  • 일단 BFS를 진행하며, 접근한 순서를 기록해둔다.
  • 접근하려는 정점들의 순서를 확인한다.
  • 접근하려는 정점이 이전보다 줄었거나, 이전과 2단계 이상 차이나면 오답처리한다.
  • 해당 방법은 반례가 있었는지 50% 에서 오답처리되었다

주의할 점

  • 시작점은 반드시 1 이여야한다. 문제조건
  • 큐에 넣는 순서도 조심해야한다.
    • input에 맞춰서 BFS를 진행해야한다.
    • 접근하려는 원소를 큐에 넣어서 비교해야한다.
    • 나의 경우 한번에 큐에 다 때려넣고, 원소 유무만 확인 한후 BFS를 진행하여 오답처리되었다.

풀이

입력받는 순서대로 접근하기 위해 큐를 이용했다.

  • input에 맞춰서 BFS를 진행해야한다.
  • FIFO 방식을 이용하기 위해 큐를 이용했다.

BFS를 진행한다.

  • 각 정점에서 BFS를 통해 접근 가능한 다른 정점들을 set에 저장 한다.
    • set을 이용한 이유는 존재 여부를 빠르게 확인하기 위해 사용했다.
  • set에 들어가 있는 정점들은 다음에 전부 접근 할 수 있는 목록들이다.
    • 접근하려는것이 set에 없다면, 잘못된 접근 순서이다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;

vector<int> node[100002];
queue<int> input_q, bfs_q;

int visit[100002];
int n;

bool bfs(){

    while(!bfs_q.empty()){
        int cur = bfs_q.front(); bfs_q.pop();

        unordered_set<int> s;

        for(int connect_node : node[cur]){
            if(visit[connect_node]) continue;
            visit[connect_node] = true;
            s.insert(connect_node);
            //  bfs_q.push(maybe_connect);
            //  이렇게 넣어버리고 한번에 처리하면, BFS 순서가 꼬여버린다.

        }

        for(int i = 0; i < (int)s.size(); ++i){
            if(input_q.empty()) return false;

            int maybe_connect = input_q.front(); input_q.pop();
            if(s.find(maybe_connect) == s.end()) return false;
            bfs_q.push(maybe_connect);
            //  fixed : input_q의 순서를 따라가야 하기 때문에 
            // 접근하려는 정점이 목록에 있는지 확인하고, 있는 경우에 bfs_q에 넣는다. 
        }
    }

    return true;
}



bool solve() {
    int start = input_q.front(); input_q.pop();
    if(start != 1) return false;

    visit[start] = true;
    bfs_q.push(start);

    return bfs();
}

void input() {
    cin >> n;
    int a, b;
    for(int i = 0; i < n - 1; ++i){
        cin >> a >> b;
        node[a].push_back(b);
        node[b].push_back(a);
    }

    int num;
    for(int i = 0; i < n; ++i){
        cin >> num;
        input_q.push(num);
    }
}

int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);  cout.tie(NULL);
   freopen("input.txt", "r", stdin);

   input();

   if(solve()) cout << 1 << "\n";
   else cout << 0 << "\n";

   return 0;
}

피드백

반례를 생각하는 능력을 좀 더 키우자.