[백준/C++] 16964번_DFS 스페셜 저지

문제는 다음과 같습니다.

이 문제도 bfs 스페셜 저지에서 정렬을 이용한 것처럼,
인접리스트를 입력받은 배열 순으로 정렬해서
먼저 정렬을 적용한 후에 dfs를 수행했습니다.

풀이는 다음과 같습니다.

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

vector<int> v[100001]; int ch[100001]={0, }; int a[100001]={0, };
vector<int> res; vector<int> cp;

bool cmp(int t1, int t2){
  return a[t1]<a[t2];
}

void DFS(int n){
  res.emplace_back(n);

  for(int i=0; i<v[n].size(); i++){
    if(ch[v[n][i]]==0){
      ch[v[n][i]]=1;
      DFS(v[n][i]);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin>>n;
  for(int i=0; i<n-1; i++){
    int t1, t2; cin>>t1>>t2;
    v[t1].emplace_back(t2); v[t2].emplace_back(t1);
  }
  for(int i=1; i<=n; i++){
    int tmp; cin>>tmp; a[tmp]=i;
    cp.emplace_back(tmp);
  }
  if(a[1]!=1) { cout<<"0"; return 0; } // 예외처리

  for(int i=1; i<=n; i++) sort(v[i].begin(), v[i].end(), cmp);
  ch[1]=1;
  DFS(1);

  if(cp==res) cout<<"1";
  else cout<<"0";
  return 0;
}

2/20 일 복습)

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

int a[100001]={0, }; vector<int> v[100001]; int ch[100001]={0, }; int n;
vector<int> res; int idx=0; int state=1;

bool cmp(int t1, int t2){
  return a[t1]<a[t2];
};

void DFS(int k){
  if(k!=res[idx++]){
    state=0;
    return;
  }
  ch[k]=1;
  for(int i=0; i<v[k].size(); i++){
    if(ch[v[k][i]]==0){
      DFS(v[k][i]);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  cin>>n;
  for(int i=0; i<n-1; i++){
    int t1, t2; cin>>t1>>t2;
    v[t1].emplace_back(t2); v[t2].emplace_back(t1);
  }
  for(int i=0; i<n; i++){
    int tmp; cin>>tmp; a[tmp]=i; res.emplace_back(tmp);
  }
  if(res[0]!=1) { cout<<"0"; return 0; }
  
  for(int i=1; i<=n; i++){
    sort(v[i].begin(), v[i].end(), cmp);
  }
  DFS(res[0]);
  
  if(state) cout<<"1";
  else cout<<"0";
  return 0;
}