백준 / 실버 1 / 11725 트리의 부모 찾기 / Python [그래프]

그래프에 약하다. 우선은 감이 안와서 참고했다.

그래프를 만나면 취할 행동

1. 양방향 그래프를 위한 이중 리스트 graph, 순회를 위한 리스트 visited을 선언한다

graph = [[] for _ in range(N+1)]
visited = [False for _ in range(N+1)]

2. 그래프에 담는다

for _ in range(N):
	a, b = map(int, input().split()
    graph[a].append(b)
	graph[b].append(a)

3. 순회를 위한 dfs 함수를 작성한다
   재귀 작성할 땐 sys.setrecursionlimit(10**6) 빼먹지 않는다.

def dfs(v, visited, result):
	visited[v] = True
    for i in graph[v]:
	    if not visited[i]:
        	순회하면서 할 행동
            dfs(i, visited, result)

풀이

visited랑 parent 배열을 따로 하는 것이 정석이지만
여기선 약간의 기교 및 최적화로 생략하였다.
visited한 노드는 parent값이 무조건 채워지기 때문이다.
코테에서는 이런 거 고민하지 말고 무조건 정석대로 하자.

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

N = int(input())
graph = [[] for _ in range(N+1)]
visited = [None for _ in range(N+1)]

def dfs(v, visited):
    for i in graph[v]:
        if not visited[i]:
            visited[i] = v
            dfs(i, visited)

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

visited[1] = -1
dfs(1, visited)

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

응용: 자식 노드 출력

N = int(input())
tree = [[] for _ in range(N+1)]
visited = [False for _ in range(N+1)]
child = [[] for _ in range(N+1)]

def dfs(tree, v, visited, child):
    visited[v] = True
    for i in tree[v]:
        if not visited[i]:
            child[v].append(i)
            dfs(tree, i, visited, child)

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

dfs(tree, 1, visited, child)

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