[DFS/BFS] 깊이우선탐색과 너비우선탐색

문제

입출력

💡 사고의 흐름

• DFS : queue를 이용
• BFS : 재귀함수를 이용
• graph를 입력받고, check 함수를 활용하여 check[false]일 때 접근할 수 있도록 하여 연결된 정점 노드를 print 한다.
  DFS, BFS에 대한 기본 문제였다!
  

import sys
from collections import deque

graph = [[0 for _ in range(1001)] for _ in range(1001)]
check = [False] * 1001
def dfs(node):
  print(node, end = ' ')
  check[node] = True
  for i in range(n):
    if graph[node][i] == 1 and check[i]==False:
      check[i] = True
      dfs(i)
      
def bfs():
  check = [False] * 1001
  q = deque()
  q.append(0)
  check[0] = True
  while q:
    v = q.popleft()
    print(v, end= ' ')
    for i in range(n):
      if graph[v][i] ==1 and check[i] ==False:
        check[i] = True
        q.append(i)
if __name__=='__main__':
  n,m = map(int, sys.stdin.readline().split())
  for i in range(m):
    a,b = map(int, sys.stdin.readline().split())
    graph[a][b]=1
    graph[b][a]=1
  dfs(0)
  print('')
  bfs()