[이것이 코딩테스트다] 7일차 - DFS, BFS

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.

Chapter 5 DFS/BFS

* 학습 전 미리 알아야 할 자료구조와 함수

1. 스택, 큐

- 스택 (Stack)

   스택이란 선입후출 (First In Last Out, FILO) 자료구조로 차곡차곡 쌓아 올린 형태의 자료구조이다

스택은 python의 list로 구현이 가능하다 ( push -> append() / pop -> pop() )

 

- 큐 ( Queue )

큐란 선입선출(First In First Out) 자료구조이며 '공정한' 자료구조로 비유된다 (은행 대기줄과 같음)

파이썬의 collections 라이브러리의 deque 를 사용할 수 있다 (push -> queue.append() / pop -> queue.popleft() )

 

2. 재귀함수 

자기자신을 다시 호출하는 함수 

재귀 함수를 작성할 때 무한 루프를 방지하기 위해 함수 내에서 다시 자신을 호출한 후 그 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다는 사실과 종료 조건이 꼭 포함되어야 한다

https://dojang.io/mod/page/view.php?id=2352

 

DFS (Depth-First Search) / 깊이 우선 탐색

스택 자료구조를 활용하며 다음과 같은 실행 과정을 거친다

1. 탐색 시작 노드 (최상단 노드)를 스택에 삽입하고 방문처리
2. 최상단 노드에 인접한 노드 중 방문하지 않은 노드에 방문 -> 방문하지 않은 노드가 없다면 스택에서 상단 노드 꺼내기
3. 2번을 더이상 할 수 없을 때까지 반복

 

코드로 구현하기 

## 각 노드와 연결되어 있는 인접노드 리스트 생성

# 맨 첫번째 칸을 비운 이유 -> 노드 번호와 인덱스 일치시키기 위해
graph = [[],
         [2,3,8],
         [1,7],
         [1,4,5],
         [3,5],
         [3,4],
         [7],
         [2,6,8],
         [1,7]]

def dfs(graph, v, visited):  ## 1부터 실행
    visited[v] = True  ## 방문한 곳 
    print (v, end = ' ')
    for i in graph[v]:  ## 연결된 노드 중 가장 앞부터 탐색
        if visited[i] == False: ## 이전에 안들린 곳
            dfs(graph, i, visited) ## 재귀함수 

## 방문정보 리스트
visited = [False] * len(graph)
dfs(graph, 1, visited)

## result 
# 1 2 7 6 8 3 4 5

 

BFS (Breadth-First Search) / 너비 우선 탐색

큐 자료구조를 활용하며 다음과 같은 실행 과정을 거친다

1. 탐색 시작 노드 (최상단 노드) 를 큐에 삽입하고 방문 처리
2. 큐에서 노드를 꺼내고 해당 노드의 방문하지 않은 인접 노드를 모두 큐에 삽입하고 방문 처리
3. 2번을 더이상 할 수 없을 때까지 반복 

해당 시점에서 인접한 모드를 한번에 큐에 넣는다는 특징

- 특정 조건에서의 최단경로 문제를 해결하기 위한 풀이로 많이 사용 됨 (각 간선의 cost가 모두 같을 때)

코드로 구현하기

from collections import deque

graph = [[],
         [2,3,8],
         [1,7],
         [1,4,5],
         [3,5],
         [3,4],
         [7],
         [2,6,8],
         [1,7]]

def bfs (graph, start, visited):
    ## deque 큐 선언
    queue = deque([start])
    visited[start] = True
    ## 큐가 빌때까지
    while queue:
        v = queue.popleft()
        print (v, end = ' ')
        for i in graph[v]:
            if visited[i] == False:
                queue.append(i)
                visited[i] = True

visited = [False] * len(graph)
bfs(graph, 1, visited)

## result 
# 1 2 3 8 7 4 5 6

 

dfs, bfs 기초 코딩 및 연습문제 풀이는 깃허브에도 업로드 되어 있습니다 

GitHub - gymin97/algorithm_study: Solve the algorithm problems (python3)