본문 바로가기
알고리즘 문제풀이/백준

[백준 11725] 트리의 부모 찾기

by m2162003 2020. 10. 4.

www.acmicpc.net/problem/11725

 

11725번: 트리의 부모 찾기

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

www.acmicpc.net

포인트

- 트리 정의하기 -> 인접리스트 사용: 벡터를 사용하기

- 트리 순회하기 -> bfs: 큐를 사용하여 모든 노드를 순회한다.

 

- 주의: 매번 검색하면 시간 초과가 난다. 한번 순회하면서 부모노드를 모두 저장한다.

#include <stdio.h>
#include <vector>
#include <queue>
#define MAX 100000 + 1

using namespace std;
vector<int> v[MAX];
int result[MAX];

int root = 1;

void findParent()
{
  queue<int> q;
  int flag[MAX] = {
      0,
  };
  q.push(root);
  flag[root] = 1;

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

    for (int i = 0; i < v[cur].size(); i++)
    {
      int nxt = v[cur][i];
      if (flag[nxt])
        continue;

      result[nxt] = cur;

      q.push(nxt);
      flag[nxt] = 1;
    }
  }
}

int main(void)
{
  int n;
  scanf("%d", &n);

  for (int i = 0; i < n; i++)
  {
    int x, y;
    scanf("%d %d", &x, &y);
    v[x].push_back(y);
    v[y].push_back(x);
  }

  findParent();

  for (int i = 2; i <= n; i++)
  {
    printf("%d\n", result[i]);
  }

  return 0;
}

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 13913] 숨바꼭질 4  (0) 2020.11.01
[백준 13549] 숨바꼭질3  (0) 2020.10.29
[백준 1600] 말이 되고픈 원숭이  (0) 2020.10.29
[백준 6593] 상범빌딩  (0) 2020.10.28
[백준 7569] 토마토  (0) 2020.10.27

댓글