링크
https://www.acmicpc.net/problem/11725
문제
DFS
DFS의 정의는 깊이우선탐색이며, ‘한 점을 기준으로 파고파고들다가, 끝점에서 다시 복귀하는 과정' 을 거친다는것이 특징이다. BFS에서는 deque()를 써서 구현하지만, DFS에서는 단순 재귀만으로 구현할수 있다.
sys.setrecursionlimit(10**7)
재귀방식을 사용하는 DFS의 특성은 Python에서 무한재귀로 빠질 위험이 있다.
따라서 무한재귀를 막기위해, sys.setrecursionlimit(10**7) 를 해주는 것이 일반적이다.
DFS(코드)
def dfs(v,graph,visit):
# print(v)
visit[v] = True
for i in graph[v] :
if visit[i] == False :
result[i] = v
dfs(i,graph,visit)
dfs(1,graph,visit)
해당 노드(v)를 방문처리 하고,
연결된 노드들 중에(graph[v])
아직 방문하지않은 노드에 대해서 (visit[i] == False)
재귀를 진행한다
전체 소스코드
# graph = [[], [6, 4], [4], [6, 5], [1, 2, 7], [3], [1, 3], [4]]
# 1 - 6 - 3 - 5
# - 4 - 2
# - 7
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N = int(input().strip())
graph = [[] for _ in range(N+1)]
for _ in range(N-1) :
a, b = map(int ,input().split())
graph[a].append(b)
graph[b].append(a)
visit = [False for _ in range(N+1)]
result = [0 for _ in range(N+1)]
def dfs(v,graph,visit):
# print(v)
visit[v] = True
for i in graph[v] :
if visit[i] == False :
result[i] = v
dfs(i,graph,visit)
dfs(1,graph,visit)
for i in range(2,N+1) :
print(result[i])
'CodingTest' 카테고리의 다른 글
백준 2606 바이러스 (0) | 2022.07.13 |
---|---|
백준 14888 연산자끼워넣기 파이썬 (0) | 2022.07.08 |
백준 1260 DFS와 BFS (0) | 2022.07.05 |
프로그래머스 72411 메뉴리뉴얼 파이썬 (0) | 2022.07.01 |
백준 11660 구간 합 구하기5 파이썬 (0) | 2022.07.01 |