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

✏️ 문제

 

문제 파악

24444번 알고리즘 수업 - 너비 우선 탐색1 이 문제와 매우 유사

너비 우선 탐색으로 푸는 문제를 깊이 우선 탐색으로 똑같이 푸는 느낌이다!

 

참고로 알고리즘 수업 - 깊이 우선 탐색2 는 그냥 정렬하는 부분을 내림차순 정렬로 수정해주면 똑같이 쉽게 풀어진다~!

 

알고리즘

• 그래프 이론
• 그래프 탐색
• 깊이 우선 탐색
• 정렬

 

 

코드

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

n, m, r = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)
order = 1

for _ in range(m):
  u, v = map(int, input().split())
  graph[u].append(v)
  graph[v].append(u)

def dfs(v):
  global order
  visited[v] = order
  graph[v].sort()

  for neighbor in graph[v]:
    if visited[neighbor] == 0:
      order += 1
      dfs(neighbor)
  
dfs(r)

for i in range(n):
  print(visited[i+1])

 

 

 

---

 

⭐️ DFS와 BFS에 대해서 아직 잘 모른다면?

[알고리즘] DFS와 BFS