그래프 : DFS/BFS : 깊이우선탐색/너비우선탐색

DFS

• 재귀 함수 사용
  • 종료조건
• 스택
  • list : append, pop
• 재귀를 쓰지 않아도 가능하다

  def dfs(graph, start_node):
      need_visited, visited = list(), list()
      need_visited.append(start_node)
      
      while need_visited:
          node = need_visited.pop()
          if node not in visited:
              visited.append(node)
              for i in range(len(graph[node])-1,-1,-1) :
                  need_visited.append(graph[node][i])
      return visited

BFS

direction=[[0,1,0,-1],[1,0,-1,0]]

def bfs(x,y,graph,visited):
    q=deque([[x,y]])
    visited[x][y]=True
    while q:
        x,y=q.popleft()
        for i in range(4):
            dx,dy=x+direction[0][i],y+direction[1][i]
            if 0<=dx<n and 0<=dy<m and not visited[dx][dy]:
                q.append([dx,dy])
                visited[dx][dy]=True

• queue(큐) 사용
  • from collections import deque
    popleft(), append