[백준/Python] DFS/BFS - 1260번 DFS와 BFS

👩🏻‍🏫 풀이

# DFS
def dfs(n):
  visited[n] = True
  print(n, end=' ')
  for i in graph[n]:
    if not visited[i]:
      dfs(i)

# BFS      
from collections import deque
def bfs(n):
  queue = deque([n])
  visited[n] = True
  # 큐가 비어질때까지
  while queue:
    v = queue.popleft()
    print(v, end=' ')
    for i in graph[v]:
      # 방문하지 않은 노드라면
      if not visited[i]:
        queue.append(i)
        visited[i] = True
        
# 정점의 개수,간선의 개수,시작 정점의 번호
n, m, v = map(int,input().split())

# [[], [], [], [], []]
graph = [[] for _ in range(n+1)]

# [[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]]
for i in range(m):
  a,b = map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)
  
# 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야하므로 정렬
for i in range(1,n+1):
  graph[i].sort()

visited = [False] * (n+1)
dfs(v) # 1 2 4 3

print( )
visited = [False] * (n+1)
bfs(v) # 1 2 3 4

좋은 웹페이지 즐겨찾기