[백준/C++] 16940번_BFS 스페셜 저지

문제는 다음과 같습니다.

일단, 처음에 접근을 잘못해서 틀렸었던 문제입니다.
저는 트리의 깊이 순서대로 출력만 맞으면 맞다고 생각했습니다.
이것만 고려하고 푼 저의 풀이는 다음과 같습니다.

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

vector<int> v[100001];

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

  vector<int> v[100001]; int n; vector<int> tmp;
  int ch[100001]={0, }; int dis[100001]={0, };
  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 t; cin>>t; tmp.emplace_back(t);
  }
  if(tmp[0]!=1) { cout<<"0"; return 0; }

  queue<pair<int, int>> q;
  ch[1]=1; dis[1]=1; q.push({1, 1});

  while(!q.empty()){
    pair<int, int> p = q.front(); q.pop();
    int d = p.second; // d: distance

    for(int i=0; i<v[p.first].size(); i++){
      if(ch[v[p.first][i]]==0){
        ch[v[p.first][i]]=1; dis[v[p.first][i]]=d+1;
        q.push({v[p.first][i], d+1});
      }
    }
  }

  cout<<dis[tmp[0]]<<" ";
  for(int i=1; i<tmp.size(); i++){
    if(dis[tmp[i-1]]>dis[tmp[i]]){ // 거리가 오름차순이 있으면 틀린 경우
      cout<<"0";
      return 0;
    }
  }
  cout<<"1";
  return 0;
}

❗️하지만, 그 자식들의 순서도 그대로 고려해주어야 합니다.❗️

즉, 이를 설명하면 다음과 같습니다.

순서가 1 -> | 2 -> 4 -> 3 -> | 5 -> 6 -> 8 -> 9 -> 7
즉, 거리가 3인 경우 앞서 2 -> 4 -> 3 자식의 순서대로 나와야 한다는 것입니다.
거리 뿐만 아니라, 📌큐 자체의 순서도 고려해야 한다는 것이었습니다.📌

그래서, 개선한 방법은 다음과 같습니다.
❗️bfs 수행시 queue에 넣을 때 입력받은 배열을 넣는 것입니다.❗️
넣기에 앞서서,

• 첫번째 for문에서는 해당 연결된 자식들을 체크해주고, 이 연결된 자식들의 개수를 세줍니다.
• 두번째 for문에서는 해당 배열이 체크카 되어있는지 확인한 후, 큐에 넣습니다.

• 첫번째 for문

    int cnt=0;
    for(int i=0; i<v[p].size(); i++){
      if(ch[v[p][i]]==0){
        ch[v[p][i]]=1;
        cnt++; // cnt: 이번차례에 큐에 넣어주어야 할 개수
      }
    }

• 두번째 for문

    for(int i=idx; i<idx+cnt; i++){
      if(!ch[a[i]]){ cout<<"0"; return 0;}
      q.push(a[i]);
    }
    idx+=cnt;

전체 코드는 다음과 같습니다.

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

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

  vector<int> v[100001]; int n;
  int ch[100001]={0, }; int a[100001]={0, };
  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++) cin>>a[i];
  if(a[1]!=1) { cout<<"0"; return 0;}

  queue<int> q;
  ch[1]=1; q.push(1);
  int idx=2;

  while(!q.empty()){
    int p = q.front(); q.pop();

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

    for(int i=idx; i<idx+cnt; i++){
      if(!ch[a[i]]){ cout<<"0"; return 0;}
      q.push(a[i]);
    }
    idx+=cnt;
  } // while문 끝

  cout<<"1";
  return 0;
}

마지막으로, 중요한 것을 다시 정리하자면

✏️bfs 수행 시, 깊이가 같은 것 뿐만 아니라 "큐 순서 자체"도 고려해야 합니다.✏️

---

풀이2 : 정렬 이용

와 대박입니다.. 이런 풀이도 있었네요
여러 다른 풀이들을 참고하던 중, 아예 "정렬"로 접근하는 방법도 있었습니다.
즉, ❗️인접리스트를 입력받은 배열 순으로 정렬❗️하는 것입니다!

이를 이용하면 그냥 정렬된 인접리스트에서 bfs만 수행하면 되겠죠?

전체 코드는 다음과 같습니다.

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

int a[100001]={0, };
bool cmp(int t1, int t2){ // 정렬 기준
  return a[t1]<a[t2];
}

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

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

  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);
  queue<int> q;
  ch[1]=1; q.push(1);

  while(!q.empty()){
    int p = q.front(); q.pop();
    res.emplace_back(p);

    for(int i=0; i<v[p].size(); i++){
      if(ch[v[p][i]]==0){
        ch[v[p][i]]=1; q.push(v[p][i]);
      }
    }
  } // while문 끝

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

---

2/19 토요일 복습)

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

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

  vector<int> v[100001]; int ch[100001]={0, }; int n; queue<int> a; queue<int> q;
  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.push(tmp);
  }
  if(a.front()!=1) { cout<<"0"; return 0; }
  ch[a.front()]=1; q.push(a.front()); a.pop();

  while(!q.empty()){
    int tmp = q.front(); q.pop();
    int cnt=0;
    
    for(int i=0; i<v[tmp].size(); i++){
      if(ch[v[tmp][i]]==0){
        ch[v[tmp][i]]=1; cnt++;
      }
    }
    for(int i=0; i<cnt; i++){
      if(ch[a.front()]!=1) { cout<<"0"; return 0; }
      q.push(a.front()); a.pop();
    }
  }
  cout<<"1";
  return 0;
}

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

int a[100001]={0, };

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

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

  vector<int> v[100001]; int ch[100001]={0, }; int n; queue<int> q;
  queue<int> res;
  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.push(tmp);
  }
  if(res.front()!=1) { cout<<"0"; return 0; }
  ch[res.front()]=1; q.push(res.front());

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

  while(!q.empty()){
    int tmp = q.front(); q.pop();
    if(tmp!=res.front()) { cout<<"0"; return 0; }
    res.pop();
    
    for(int i=0; i<v[tmp].size(); i++){
      if(ch[v[tmp][i]]==0){
        ch[v[tmp][i]]=1;
        q.push(v[tmp][i]);
      }
    }
  }
  cout<<"1";
  return 0;
}