백준 11725 트리의 부모 찾기 Python3

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

11725번: 트리의 부모 찾기

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ11725_bfs.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
from collections import defaultdict
from collections import deque
N = int(sys.stdin.readline())
tree = defaultdict(list)
parent = defaultdict(int)

for _ in range(N-1):
    v1, v2 = map(int, sys.stdin.readline().split())
    tree[v1].append(v2)
    tree[v2].append(v1)
    
def bfs():
    q = deque()
    q.append(1)
    while q:
        now_v = q.popleft()
        for nv in tree[now_v]:
            if parent[nv] == 0:
                parent[nv] = now_v
                q.append(nv)
bfs()
for i in range(2, N+1):
    print(parent[i])

---

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ11725_dfs.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
from collections import defaultdict
sys.setrecursionlimit(3000000)
N = int(sys.stdin.readline())
tree = defaultdict(list)
for _ in range(N-1):
    v1, v2 = map(int, sys.stdin.readline().split())
    tree[v1].append(v2)
    tree[v2].append(v1)
    
parent = defaultdict(int)

def dfs(v, tree, parent):
    for nv in tree[v]:
        if parent[nv] == 0:
            parent[nv] = v
            dfs(nv, tree, parent)
dfs(1, tree, parent)           
for i in range(2, N+1):
    print(parent[i])

---

풀이 과정

1. BFS 활용

import sys
from collections import defaultdict
from collections import deque

N = int(sys.stdin.readline())

#인접 리스트 방식으로 그래프 표현
tree = defaultdict(list)

#key = vertex, value = vertex의 부모 노드
parent = defaultdict(int)

for _ in range(N-1):
    v1, v2 = map(int, sys.stdin.readline().split())
    tree[v1].append(v2)
    tree[v2].append(v1)
    
def bfs():
    q = deque()
    #트리의 루트인 1부터 단말 노드까지 탐색
    q.append(1)
    while q:
        now_v = q.popleft()
        
        #now_v와 인접한 노드 탐색
        for nv in tree[now_v]:
        	#인접 노드의 부모 = 현재 노드
            if parent[nv] == 0:
                parent[nv] = now_v
                q.append(nv)
bfs()
for i in range(2, N+1):
    print(parent[i])
    
#시간복잡도 = O(V+E) = O(V), 공간복잡도 = O(V)
#N = 100,000인 경우, 총 200,001번의 연산 소요
#이진 트리의 경우 최대 N-1개의 E를 갖는다

 

2. DFS 활용

import sys
from collections import defaultdict
sys.setrecursionlimit(3000000)

N = int(sys.stdin.readline())

#인접 리스트 방식으로 그래프 표현
tree = defaultdict(list)
for _ in range(N-1):
    v1, v2 = map(int, sys.stdin.readline().split())
    tree[v1].append(v2)
    tree[v2].append(v1)

#(key, value) = (vertex, vertex의 부모 노드)
parent = defaultdict(int)

def dfs(v, tree, parent):
	#v의 인접한 노드들을 탐색
    for nv in tree[v]:
    	#nv의 부모 노드는 v
        if parent[nv] == 0:
            parent[nv] = v
            dfs(nv, tree, parent)
            
#트리의 루트인 1부터 탐색
dfs(1, tree, parent)

for i in range(2, N+1):
    print(parent[i])

#시간복잡도 = O(V+E) = O(V), 공간복잡도 = O(V)
#N = 100,000인 경우, 총 200,001번의 연산 소요
#이진 트리의 경우 최대 N-1개의 E를 갖는다