[Python] 11725번 트리의 부모 찾기

✏️ 문제

 

문제 파악

위와 같이 인접 리스트로 1과 연결된 6과 4, 2와 연결된 4 ... 이렇게 구현하려면 다음과 같이 append를 사용해야 한다.

graph[a].append(b)

 

그리고 visited 배열에는 해당 인덱스의 부모 요소를 대입하여 후에 차례대로 출력하면 바로 결과값이 나오도록 구현했다.

 

알고리즘

• 그래프 이론
• 트리
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

 

코드

from collections import deque
import sys
input = sys.stdin.readline
 
n = int(input())
graph = [[] for i in range(n+1)]
visited = [0] * (n+1) 

for i in range(n-1):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a) 
 
def bfs(v):
  q = deque([v]) 
    
  while q:
    node = q.popleft()
    
    for neighbor in graph[node]:
      if visited[neighbor] == 0:
        visited[neighbor] = node
        q.append(neighbor)
 
bfs(1)
answer = visited[2:]
for x in answer:
  print(x)

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS