[백준] 11725_트리의 부모 찾기 (Python)

[문제번호]_[문제이름] (Python)

0. 출처

• 유형 : 트리 (silver 2)
• 링크 : 11725번: 트리의 부모 찾기

1. 기록

• 22/04/18 (월)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 루트노드가 1인 정보가 주어져있다.
>> 그 외의 나머지는 연결관계만 주어져있다.
>> 이 경우 부모노드를 어떻게 파악하면 좋을까?
>> 우선 연결관계부터 만들어보자.

2. 시간복잡도
>>

3. 자료구조

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
7
1 6
6 3
3 5
4 1
2 4
4 7

- 예제 출력 1 -
4
6
1
3
1
4

- 예제 입력 2 -
12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

- 예제 출력 2 -
1
1
2
3
3
4
4
5
5
6
6

(3) 코드

import sys

sys.setrecursionlimit(10**9)

n = int(input())

# 트리
tree = [[] for _ in range(n+1)]

# 부모 노드 저장
relation = [0 for _ in range(n+1)]

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

def dfs(start, tree, relation):
    # 연결된 노드들부터 relation[i] 의 부모가 없으면 부모 설정해주고 dfs를 돌린다.
    for node in tree[start]:
        if relation[node] == 0:
            # node에게 너 여기서 출발했다고 표시해주는 느낌
            relation[node] = start
            dfs(node, tree, relation)

dfs(1, tree, relation)

for i in range(2, n+1):
    print(relation[i])

(4) 정리

(5) 참고

참고 풀이