[알고리즘] DFS/BFS

그래프 표현

(인접행렬)

- 각 행과 열은 노드를 의미

- 무향 그래프일 경우 대각선 대칭

- 가중치 그래프의 경우 1이 아닌 다른 값을 넣음으로 가중치 표현

(인접 리스트)

- 각 인덱스에 해당하는 노드에 연결된 노드들을 리스트 형태로 저장한느 방식

- 가중치를 표현하기 위해서 연결정보에 튜플형태나 다른 방식으로 가중치를 추가적으로 입력

DFS(Depth First Search)

- 깊이 우선 탐색

- 갈 수 있는 한 끝까지 탐색해 leaf node를 방문하고 이전 갈림길에서 선택하지 않았던 노드를 방문

DFS

DFS 구현

- stack을 활용

1. 시작노드를 방문 표시하고 스택에 넣기
2. 스택이 비어있지 않은 동안 다음을 반복합니다.
2-1. 스택의 최상단 노드를 꺼냅니다.
2-2. 꺼낸 노드에 방문하지 않은 인접 노드가 있다면 그 노드를 스택에 넣고 방문 처리
2-3. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼냄

DFS 코드 구현(인접리스트)

def dfs(graph:Dict, start:int):
    visited = {i:False for i in graph.keys()}
    stack = [start]
    
    while stack:
        node = stack.pop()
        
        if not visited[node]:
            visited[node] = True
            stack.extend(graph[node])

BFS(Breadth First Search)

- 너버 우선 탐색

- 시작점인 루트 노드와 같은 거리에 있는 노드를 우선으로 방문

BFS

BFS 구현

- queue를 활용

- 노드를 방문하면서 인접한 노드 중 방문하지 않은 노드의 정보만 큐에 넣어 먼저 큐에 들어있던 노드부터 방문

1. 시작 노드를 큐에 넣고 방문 표시를 합니다.
2. 큐가 비어있지 않는 동안 다음을 반복합니다.
2-1. 큐의 가장 앞 노드를 꺼냅니다.
2-2 해당 노드와 연결된 인접 노드를 큐에 추가하고 방문 표시를 합니다.

BFS 코드 구현

from collections import deque

def bfs(graph:Dict, start:int):
    visited = {i:False for i in graph.keys()}
    queue = deque([root])
    visited[start] = True

    while queue:
        current = queue.popleft()
        for next in graph[current]:
            if not visited[next]:
                queue.append(next)
                visited[next] = True

 

예제 문제들