[CLASS 4]백준 11725번 - 트리의 부모 찾기

11725번 : 트리의 부모 찾기

 

핵심적인 생각은, 노드를 받고 각각의 노드 마다 자신이 어떤 노드와 연결되었는지를 저장한 뒤에, 1번 노드부터 시작해서 자신과 연결된 노드를 자식 노드로 설정하고, 그 뒤부터는 DFS혹은 BFS를 돌리면서 계속 자신이 연결된 노드(이미 부모 노드가 정해진 노드 제외)를 자식 노드로 삼으면된다.

 

내 코드(BFS):

# dawitblog.tistory.com
from sys import stdin
from collections import deque
input = stdin.readline

n = int(input())
roots = [0]*(n+1)
connections = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int,input().split())
    connections[a].append(b)
    connections[b].append(a)

queue = deque([1])
roots[1] = True
while queue:
    root = queue.popleft()
    for child in connections[root]:
        if not roots[child]:
            roots[child] = root
            queue.append(child)

print(*roots[2:],sep='\n')

 

입력을 받을 때 connections 리스트에 자신이 연결된 노드를 모두 저장하고, BFS를 통해 탐색하면서 자식 노드의 부모 노드를 설정해 주었다.

 

내 코드(DFS):

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline

n = int(input())
roots = [0]*(n+1)
connections = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int,input().split())
    connections[a].append(b)
    connections[b].append(a)

stack = [1]
roots[1] = True
while stack:
    root = stack[-1]
    l = len(stack)
    for child in connections[root]:
        if not roots[child]:
            roots[child] = root
            stack.append(child)
            break
    if l == len(stack):
        stack.pop()

print(*roots[2:],sep='\n')

 

DFS를 스택을 이용하여 구현했는데 시간이 무려 3056ms나 걸린다. 사실 정직하게 깊이 우선 탐색의 순서를 지킬 필요는 없다. 무지막지하게(?) 탐색하더라도 이미 부모 노드를 결정한 노드의 부모 노드를 수정하지만 않으면 되기 때문에 이렇게 작성해도 된다.

 

내 코드:

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline

n = int(input())
roots = [0]*(n+1)
connections = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int,input().split())
    connections[a].append(b)
    connections[b].append(a)

stack = [1]
roots[1] = True
while stack:
    root = stack.pop()
    for child in connections[root]:
        if not roots[child]:
            roots[child] = root
            stack.append(child)

print(*roots[2:],sep='\n')