[Solved] BOJ: 11725 | 트리의 부모 찾기

문제

주어진 연결 상태로 트리를 만들어
각 노드의 부모노드 구하기

입력

• 첫번째 줄: 트리 길이 t
• 두번째 줄~2+t-1: 노드 연결 상태

출력

각 노드의 부모 노드 출력

---

접근

• 일단 연결 상태를 가지고 트리를 만든 후
• dfs로 부모 노드를 구하면 되겠...다?

풀이

입력 및 트리 만들기

n = int(input())
tree = {}

# make tree
for _ in range(n-1):
    n1, n2 = map(int, input().split())
    if n1 in tree:
        tree[n1].append(n2)
    else:
        tree[n1] = [n2]

    if n2 in tree:
        tree[n2].append(n1)
    else:
        tree[n2] = [n1]

• dictionary를 이용해 트리를 만들었다

dfs

# dfs
visited = [0 for _ in range(n+1)]
def dfs(r):
    for node in tree[r]:
        if visited[node] == 0:
            visited[node] = r
            dfs(node)

• 루트노드에 연결되어있는 여러 노드들에 대해
• 방문한 적이 없는 노드라면 (0이라면)
• 방문 표시 인덱스에 부모 노드 값 넣어 줌 -> 0이 아니기때문에 방문처리도 동시에 됨
• 그 노드로 다시 dfs

출력

dfs(1)

for j in range(2, len(visited)):
    print(visited[j])

• 시작을 1로 하여 dfs를 돌리고
• visted 리스트의 각 인덱스에 적힌 값(부모 노드 값) 출력

---

전체 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
tree = {}

# make tree
for _ in range(n-1):
    n1, n2 = map(int, input().split())
    if n1 in tree:
        tree[n1].append(n2)
    else:
        tree[n1] = [n2]

    if n2 in tree:
        tree[n2].append(n1)
    else:
        tree[n2] = [n1]

# dfs
visited = [0 for _ in range(n+1)]
def dfs(r):
    for node in tree[r]:
        if visited[node] == 0:
            visited[node] = r
            dfs(node)

dfs(1)

for j in range(2, len(visited)):
    print(visited[j])

• 정말 기본적인 dfs 문제
• 기본적이고 뭐고 다 까먹어서 헤맸다ㅠ.ㅠ

---

제출

Recursion Error

sys.setrecursionlimit(10**6)

• 재귀 제한 늘려서 해결