[코딩테스트] DFS / BFS 코드 예시

참고 이것이 취업을 위한 코딩 테스트다 with 파이썬

https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC

---

 

 

DFS 동작 예시

def dfs(graph, v, visited):
    visited[v] = True # 현재 노드를 방문 처리
    print(v, end=' ')
    
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

visited = [False] * 9

dfs(graph, 1, visited)

## 출력
## 1 2 7 6 8 3 4 5

 

BFS 동작 예시

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])  # Queue 구현을 위해 deque 라이브러리 사용
    visited[start] = True  # 현재 노드를 방문 처리
    
    # queue가 빌때까지 반복
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        # 아직 방분하지 않은 인접한 원소들을 queue에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

# 각 노드가 연결된 정보를 표현 (2차원 리스트)
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

visited = [False] * 9

bfs(graph, 1, visited)

##출력
## 1 2 3 8 7 4 5 6