[백준] 11725번 트리의 부모 찾기 - 파이썬

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

11725번: 트리의 부모 찾기

풀이

트리를 만든 뒤 노드 2번부터 N번까지의 부모를 출력하는 것이 목표입니다.

자식을 찾기 위해서 저는 트리의 루트인 1번을 시작으로 자식을 찾아주었습니다. 1번 노드와 연결되어있는 노드들을 나타내는 리스트의 노드들은 부모가 아닌 무조건 자식이기 때문입니다.

중복된 노드를 다시 집어넣어서 자식을 찾지않게 주의하여 코드를 짭니다.

 

재귀함수 풀이

# 11725번 트리의 부모 찾기
import sys
sys.setrecursionlimit(10 ** 9)

n = int(input())
tree = [[] for _ in range(n+1)]
ans  = [0]*(n+1)

for _ in range(n-1):
    a, b = map(int, sys.stdin.readline().split())
    tree[a].append(b)
    tree[b].append(a)

# 중복처리를 위한 집합
s = set([1])

def findParent(root):
    for i in tree[root]:
        if i not in s:
            ans[i] = root
            s.add(i)
            findParent(i)

def PrintAns():
    for i in ans[2:]:
        print(i)

findParent(1)
PrintAns()

출력결과(재귀함수를 이용한 풀이)

 

 

리스트를 이용한 풀이

# 11725번 트리의 부모 찾기
import sys

n = int(input())
tree = [[] for _ in range(n+1)]
ans  = [0]*(n+1)

for _ in range(n-1):
    a, b = map(int, sys.stdin.readline().split())
    tree[a].append(b)
    tree[b].append(a)

# 불필요한 계산을 없애기 위해 루트 부모는 본인으로 설정.
ans[1] = 1
# 부모부터 시작해서 자식노드를 찾기 위해 노드 1번 추가.
temp = [1]

def findParent(root):
    while temp:
        cur = temp.pop()
        for i in tree[cur]:
            if not ans[i]:
                ans[i] = cur
                temp.append(i)

def PrintAns():
    for i in ans[2:]:
        print(i)

findParent(1)
PrintAns()

출력결과(리스트를 이용한 풀이)