[ 백준 / 파이썬 ] 11725. 트리의 부모 찾기

 

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

11725번: 트리의 부모 찾기

🎉🎉 문제

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

 

 

🎉🎉 풀이

✅ 1번을 루트노드로 어떤 노드가 자식들을 갖는지 기록한다

✅ 부모가 가진 자식들을 탐색하며 출력하는 경우 100,000 * 100,000으로 시간초과가 난다

✅ 고민하다가 자식이 어떤 부모를 가지는지 기록하면 for문 한 번(100,000의 연산)만으로 출력이 가능할 것이라고 생각해 그 과정을 추가하니 통과

 

 

🎉🎉 코드

from collections import deque

n = int(input())
graph = [[] for _ in range(n+1)]

for _ in range(n-1):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

parents = [[] for _ in range(n+1)] #부모를 인덱스로 자식을 기록하는 그래프

queue = deque()
queue.append(1) #루트 노드 1부터 시작
visited = [False]*(n+1)

while queue:
  v = queue.popleft()
  visited[v] = True
  for i in graph[v]:
    if not visited[i]:
      parents[v].append(i) #부모 아래에 있는 자식들을 추가
      queue.append(i)

#여기서 부모를 for문 2번으로 탐색하면 시간초과가 난다
#시간초과를 막기 위해 자식이 어떤 부모를 갖게 되는지 기록해 for문 한 번으로 100,000번의 연산만 수행

children = [[] for _ in range(n+1)] 
for i in range(1, len(parents)):
  for j in parents[i]:
    children[j].append(i)
    
for i in range(2, n+1):
  print(children[i][0])

 

---

시간초과 코드 ㅠ ㅠ

from collections import deque

n = int(input())
graph = [[] for _ in range(n+1)]

for _ in range(n-1):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

parents = [[] for _ in range(n+1)]

queue = deque()
queue.append(1)
visited = [False]*(n+1)

while queue:
  v = queue.popleft()
  visited[v] = True
  for i in graph[v]:
    if not visited[i]:
      parents[v].append(i)
      queue.append(i)

for i in range(2, n+1):
  for j in range(1, n+1):
    if i in parents[j]:
      print(j)
      break