[백준 / BOJ] C++ 16940 BFS 스페셜

16940번: BFS 스페셜

 

문제

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

16940번: BFS 스페셜 저지

 

 

풀이

스페셜 저지 문제는 답이 여러 개가 가능한 문제다. 이런 경우 답이 맞는지 확인하는 코드가 필요하다. BFS의 결과가 가능한지 구하는 문제다. BFS는 간선의 순서에 따라 이동하는 순서가 바뀐다. 그래서 간선의 순서를 유저가 입력한 답과 같이 이동하도록 재정렬 해줘야 한다. 어떤 순서로 정점을 방문하는지를 저장하는 order 배열을 만들고 먼저 방문해야 하는 정점과 연결된 간선이 앞으로 오도록 간선들을 재정렬 한다. 그리고 BFS를 진행하며 탐색 경로를 구한다. 이 경로가 주어진 경로와 같으면 1, 다르면 0을 출력한다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, cnt = 0;
vector<int> graph[100001], visited(100001, 0), v(100001, 0), order(100001, 0), way(100001, 0);

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

void bfs(int s) {
  queue<int> q;
  q.push(s);
  visited[s] = 1;
  way[cnt++] = s;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int y : graph[x])
      if (!visited[y]) {
        q.push(y);
        visited[y] = 1;
        way[cnt++] = y;
      }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n;
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  for (int i = 0; i < n; i++) {
    cin >> v[i];
    order[v[i]] = i;
  }
  for (int i = 1; i <= n; i++)
    sort(graph[i].begin(), graph[i].end(), cmp);
  bfs(1);
  cout << (way == v ? 1 : 0) << '\n';
  return 0;
}