[백준/BOJ] 11725번 : 트리의 부모 찾기 _Python

11725번: 트리의 부모 찾기

 

>문제

>접근방법

   트리도 그래프의 유형 중 하나이기 때문에 bfs를 이용한다. 부모노드에 인접한 노드를 자식노드로 간주하고, 자식노드 인덱스의 값을 부모노드로 채워준 리스트를 만들어서 출력하면 된다.

 

 

>풀이법

   주석으로 대체

 

 

>코드

from collections import deque

n = int(input()) # 노드의 개수
tree = [[]*n for _ in range(n+1)] # 트리의 노드 정보
queue = deque([]) # 큐의 원소는 부모노드의 역할
visited = [False for _ in range(n+1)] # 방문한 노드 확인
result = [[]*n for _ in range(n+1)] # 결괏값을 담을 리스트

# 트리의 노드 정보를 입력
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

# 루트를 1로 설정 후 방문처리
queue.append(1)
visited[1] = True

# 부모노드 찾기(using 너비우선탐색)
def bfs():
    while queue:
        a = queue.popleft() # 큐에서 원소를 꺼낸다. 이후 a는 부모노드가 됨
        for i in tree[a]: # a에 인접해 있는 노드를 하나씩 검색 (-> a의 자식노드들 검색)
            if not visited[i]: # 아직 방문한 적 없는 경우에만
                queue.append(i) # 자식노드 i를 큐에 삽입
                visited[i] = True # 방문처리
                result[i] = a # i번째 노드의 부모는 현재 a 라는 정보를 리스트에 담기

bfs()

# 리스트 출력
for i in result:
    if i: # 빈 원소는 빼고
        print(i)

 

 

>결과

 

 

>결론

오늘 고구마만 먹었더니 몸이 허하다