DFS/BFS 알고리즘

📌DFS, BFS를 알아보기전 알아야하는 자료구조와 개념

탐색(search)

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.

 

스택(stack)

- FILO(First In Last Out): 박스 쌓기

- list로 간편하게 구현 가능(삽입: append, 삭제: pop)

- 시간복잡도: O(1)

 

큐(queue)

- FIFO(First In First Out): 입구랑 출구가 모두 뚫려있는 터널

- from collections import deque(삽입: append, 삭제: popleft)

- 시간복잡도: O(1)

 

재귀함수(recursive function)
- 자기 자신을 다시 호출하는 함수
- python 에서는 '최대 재귀 깊이 제한'이 있기 때문에 별다른 설정이 없다면 오류메세지와함께 종료되게 된다.
- 일반적인 문제풀이 경우(일부러 무한루프를 만들지 않는 경우)에는 재귀 함수의 종료 조건을 반드시 명시해야 한다.
- 모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.
- 컴퓨터가 함수를 재귀적으로 호출하게 되면, 컴퓨터 메모리 내부의 스택 프레임에 쌓이게 된다.
=> 이러한 특징때문에 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀함수를 이용하는 경우가 있다.
(ex. 단순히 더 짧고 간결하게 작성하기위해(dfs))

---

🔵DFS(Depth First Search)

- 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
- 스택 자료구조(or 재귀함수)를 이용한다.
=>  1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
    2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있다면, 그 노드를 스택에 넣고 방문 처리를 한다.
       방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
       **즉, 매번 최상단 노드를 기준으로 방문하지 않은 인접노드가 있으면 그 인접한 노드로도 방문을 수행하는 것.
    3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

- 그래프 문제가 출제되면 노드의 번호가 1번부터 시작하는 경우가 많기 때문에 list의 0번 index는 비우고 index 1부터 시작하도록 한다.

 

🔵BFS(Breadth First Search)

- 너비 우선 탐색, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
- 큐 자료구조를 이용한다.
=>  1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
    2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
       **해당 시점에서 인접한 노드를 '한번에' 모두 큐에 넣는다는 것이 특징이다.
    3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

DFS 소스코드 예제

#재귀함수를 통한 구현
def dfs(graph, v, visit): #visit; 방문 처리 여부가 기록되어 있는 리스트
    visit[v] = True     #해당 노드를 방문처리 해줌
    print(v, end=' ')   #그 노드를 방문했다는 의미로 해당 노드를 출력할 수 있도록 함

    #현재 확인하고 있는 = 스택의 최상단 노드에 해당하는 원소와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visit[i]:        #만약 그 노드가 = 즉 인접한 노드가 방문되지 않은 상태라면, 
            dfs(graph, i, visit)    #재귀 함수를 이용해 방문을 진행한다

#2차원 리스트 형태로 각 노드가 연결된 정보를 표현해줌
graph = [
    [],     #노드의 번호가 1번부터 시작하는 경우가 많기 때문에 편의상 0번 INDEX를 비워줌 
    [2, 3, 8],  #인덱스 기준으로 연결을 표현해줌; 1번 노드와 연결된건 2, 3, 8 번 노드라는 뜻
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

#기본적으로 모든값들을 False값으로 초기화해서 처음에는 모든 노드를 방문하지 않은 것 처럼 처리할 수 있다.
#index 0을 사용하지 않게 하기위해 9를 곱함
#방문처리를 위해 하나의 1차원 리스트를 만들어줌
visit = [False] * 9

dfs(graph, 1, visit)

 

BFS 소스코드 예제

from collections import deque

def bfs(graph, start, visited):

    #시작 노드를 queue에 넣어줌.
    queue = deque([start])

    #시작 노드를 방문처리한다.
    #방문 처리란, 스택에 한 번이라도 삽입된 노드를 다시 삽입하지 않도록 체크하는 것을 의미합니다. 즉, 방문 처리를 함으로써 각 노드를 한 번씩만 처리할 수 있게 합니다.
    visited[start] = True

    #이후에 큐가 빌때까지 = 더이상 수행할 수 없을 때 까지 반복한다.
    while queue:

        v = queue.popleft()         #큐에서 원소를 하나 꺼낸다.
        print(v, end=' ')

        for i in graph[v]:          #꺼낸 노드와 인접한 노드를 하나씩 확인
            if not visited[i]:      #아직 방문하지 않은게 있다면
                queue.append(i)     #큐에 다 넣어주도록 한다.
                visited[i] = True


#각 노드가 연결된 정보를 표현(그래프를 표현한 부분)
graph = [
    [],         #0번 노드에 대한 부분은 비워준다.(사용x)
    [2,3,8],    #1번 노드가 인접해있는 노드들
    [1,7],      #2번 노드가 ...
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7],
]

#방문처리 목적으로 visited 리스트를 만들어줌
visited = [False]*9

bfs(graph, 1, visited)

 

 

*이것이 취업을 위한 코딩 테스트다 2021 유튜브 강의를 참고하여 작성했습니다.