알고리즘/DFS BFS
[Python] 백준 24481 알고리즘 수업 DFS (재귀!!!)
JayAlex07
2023. 2. 11. 14:00
🧑💻 [Python] 백준 24481 알고리즘 수업 DFS (재귀!!!)
Silver 2 - DFS
시작 기준에서 각 노드까지 얼마나 걸리는지 찾는다
문제풀이
- 재귀를 이용하여 DFS를 실행한다
sys.setrecursionlimit(10 ** 6)
input=sys.stdin.readline
- 재귀를 제한해주는 식이다 (코딩 테스트에서 재귀를 사용할 때에 꼭 필요하다)
코드
import sys
sys.setrecursionlimit(10 ** 6)
input=sys.stdin.readline
def dfs(start, count):
result[start] = count
for num in tree[start]:
if result[num] == -1:
dfs(num, count + 1)
n, m, r = map(int, input().split())
tree = [[] for _ in range(n + 1)]
result = [-1] * (n+1)
for _ in range(m):
a, b = map(int, input().split())
tree[a].append(b)
tree[b].append(a)
for t in tree:
t.sort()
dfs(r, 0)
for i in range(1, n+1):
print(result[i])