[BOJ] 알고리즘 수업 - 깊이 우선 탐색 1

아래 백준 로고를 클릭하면 해당 문제로 이동합니다 😀

풀이과정

---

문제에 의사코드를 친절히 주셨다.
의사코드에 맞춰서 일단 dfs 틀을 잡아두고, 내가 작성한 코드에 맞춰 수정해줬다.

근데 백준에서 런타임에러가 계속 떴다..
팡연이가 recursion depth때문이라고 sys.setrecursionlimit(10**8)코드를 추가해줬다.

구현한 dfs 코드가 재귀이고, 일정 깊이 이상으로 못들어가게 리미트가 걸려있어서 그걸 해제하는거라고 한당 .. 암튼 해결!

코드

---

import sys
sys.setrecursionlimit(10**8)

N, M, R = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

for i in range(1, N+1):
    graph[i].sort()

visited = [False] * len(graph)
result = [0 for _ in range(N+1)]
t = 1

def dfs(graph, r, visited):
    global t

    visited[r] = True
    result[r] = t
    t += 1

    for node in graph[r]:
        if not visited[node]:
            dfs(graph, node, visited)

dfs(graph, R, visited)

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

결과

---