[C/C++] 백준 11725: 트리의 부모 찾기(vector 이용)

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

11725번: 트리의 부모 찾기

11725: 트리의 부모 찾기

 

맨 처음에 문제에서 트리의 루트를 1로 둔다는 조건을 확인 못해서 맨 처음에 해맸다..

 

구현!!

 사실 간단하게 풀이가 가능하다. 이차원 백터 vector<int>v1[100001]를 선언하여 각 노드와 연결되어 있는 노드를 뒤에 추가해주면 된다. 이때 무엇이 부모이고 자식 노드인지 모르기 때문에

 

v1[tmp1].push_back(tmp2);
v1[tmp2].push_back(tmp1);

두번 다 해줘야한다.

 

 그 다음에는 queue를 이용하여 push와 pop을 해주면 되는데 이미 v1 백터의 값을 넣어줬기 때문에 i번째 노드가 이번에 pop될 차례이면 이 값과 연결된 노드가 있는지 확인한다. 확인을 한 후에 한번도 지나가지 않은 자식노드 j가 있다면 result 배열에 연결된 노드의 부모 노드, 즉 i번째 노드를 저장하고 j번째 노드를 push 해준다

 이 과정을 i번째 노드의 자식이 없을 때까지 반복을 하며 queue에 남은 원소 값이 없을 때까지 반복하여 result 값에 저장해줘야 한다.

 

 이때 result 배열의 역할이 중요한데, result[j]가 없다면  현재 위에서 무엇이 부모이고 자식 노드인지 모르기 떄문에 입력받은 두 값을 모두 v1 백터의 넣어줬으므로 cycle이 생겨 무한히 돌거나 값이 달라질 수 있다. 그렇기 때문에 이미 한 번 확인한 노드의 부모노드 값을 result 배열에 저장시켜 이런 일이 없도록 만들어줘야 한다.

 

 또한 사실 queue에서 빠져나가는 순서대로 트리의 차수가 높으니 (물론 같을 수 있다) 이 점 참고하여 문제를 풀면 어렵지 않게 풀 수 있다!

 

소스코드!

#include <iostream>
#include <algorithm>
#include<queue>
#include<tuple>
#include <string.h>
#include <map>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역

vector<int>v1[100001];
queue<int> q1;
int result[100001];


int main() {
  int n;
  cin>>n;
  for(int i=1;i<n;i++)
    {
      int tmp1,tmp2;
      cin>>tmp1>>tmp2;
      v1[tmp1].push_back(tmp2);
      v1[tmp2].push_back(tmp1);
    }
  q1.push(1);
  result[1]=1;
  while(q1.size()!=0)
    {
      int tmp=q1.front();
      for(int i=0;i<v1[tmp].size();i++)
        {
          int k=v1[tmp][i]; //자식 노드
          if(result[k]==0){ //한번도 지나가지 않았다
            result[k]=tmp; // 자식 노드의 부모노드 저장
            q1.push(k);
          }      
        }
      q1.pop();
    }

  for(int i=2;i<=n;i++)
    cout<<result[i]<<"\n";
}