[BOJ] 11725. 트리의 부모 찾기(Python) / BFS, DFS

11725번: 트리의 부모 찾기

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

# 26분 소요

• 사용 알고리즘 : Stack을 이용한 루트 노드 구하기
• Stack을 이용한 기본적인 코드로 아래 주석으로 설명을 대신한다.

 

Stack을 사용해 푼 파이썬 코드는 다음과 같다.

(아래 코드에서 stack만 queue로 바꿔 head부터 pop하면 BFS로 푼 코드가 된다.) 

---

from sys import stdin
input = stdin.readline

def solve():
    parentNode = {i: 0 for i in range(1, N+1)}
    parentNode[1] = 1	# 루트 노드 1 방문 표시
    stack = [1]			# 스택에 담기
    while stack:
        x = stack.pop()
        for nx in connectInfo[x]:
            if parentNode[nx]:		# 이미 방문했으면 넘기기
                continue
            parentNode[nx] = x      	# 부모 노드로 방문 표시
            stack.append(nx)		# 스택에 담기

    # 출력
    for i in range(2, N+1):
        print(parentNode[i])
    
# main
N = int(input())   # 연결 정보 저장
connectInfo = {i: [] for i in range(1, N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    connectInfo[a].append(b)
    connectInfo[b].append(a)
solve()

---

• 시간 : 316ms / 메모리 : 152936kb(PyPy3 제출)
• 고찰 : 실버2 난이도. 스택과 큐로 간단하게 노드의 부모 노드 찾기 문제였다. Keep Going