DFS, BFS

탐색은 많은 양의 데이터 중 원하는 데이터를 찾는 과정이다. 

그래프, 트리 등의 자료구조 안에서 탐색 하는 문제를 주로 다룬다. 

대표적으로 DFS, BFS 를 꼽고, 이 두 알고리즘은 원리를 완벽하게 이해해야 문제 해결이 가능하다. 

두 알고리즘의 원리가 되는 Stack, Queue 를 간단하게 살펴보자. 

 

STACK

스택은 박스쌓기를 기억하면 잊지 않을 수 있다 .

다음과 같이 박스를 쌓으면 맨 하단의 박스가 당연히 가장 먼저 내려놓은 박스이다. 그러나 우리가 다시 박스를 들어올릴 때는 최 상단의 박스부터 들어올리게 된다. 

즉, 처음에 넣은 것이 (First in) 가장 마지막에 나오게 된다(Last out). 

 

QUEUE 

큐는 버스를 생각하면 잊지 않을 수 있다. 

 

버스는 한쪽 입구로 타서 안쪽 출구로 내린다. 모든 사람이 동일한 목적지를 향한다고 가정할 때, 먼저 탄 사람이 입구로 들어오는 사람들에게 밀려 점차 출구쪽에 배치되고, 당연히 내리는 순서는 탄 순서대로 내리게 된다. 

즉, 처음 넣은 것이(First in) 가장 처음 나오게 된다.(First out) 

 

Stack 은 그냥 list 를 사용해서 append 하고, 빼낼 때는 pop 으로 맨 뒤 원소를 빼내면 된다. 

 

Queue 는 collections libaray의 deque 함수를 사용한다. 

deque 는 스택과 큐의 장점을 모두 채택한 자료구조 인데, 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이면 queue 라이브러리를 이용하는 것보다 더 간단하다. 

아래와 같이 사용한다. 

from collections import deque 

queue = deque()

queue.append(5)
queue.popleft()

직관적으로는 함수가 queue.push, queue.pop(0) 의 형태일 것이라고 기대되지만 

실제로 함수의 명칭은 append 와 popleft() 이다. 우선 stack의 장점을 차용했기에 추가가 append 로 된다고 이해하면 될 것 같고, 

pop(0) 은 list 에서도 사용하는 함수이다. popleft 가 더 빠르게 구현된 것으로 보인다. 

 

DFS, BFS 를 구현하려면 재귀함수도 이해해야 한다. 

 

재귀함수

재귀함수는 종료조건을 반드시 명시해야 한다. 

컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 사용한다. 

컴퓨터 구조 측면에서 보면 연속해서 호출되는 함수는 메인 메모리의 스택 공간에 적재되므로 재귀함수는 스택 자료구조와 같다는 말이 틀린 말이 아니다. 

 

간단하게 팩토리얼 문제를 재귀로 구현해보자. 

import argparse

parser = argparse.ArgumentParser(description='N')

parser.add_argument('--fact',          type=int,   default=5)

args = parser.parse_args()

def factorial(n):
    if n == 1:
        return 1 
    else:
        return n * factorial(n-1)

print(factorial(args.fact))

#print(args.__dict__)

 

그래프

그래프는 노드와 간선으로 표현되며 노드를 정점이라고도 한다. 

 

그래프 표현 방식은 크게 2가지가 있다.

• 인접 행렬 (Adjacency Matrix): 2차원 배열로 그래프 연결 관계 표현 

2차원 배열에 각 노드가 연결된 형태를 기록하는 방식. 2차원 리스트로 구현 가능하다. 연결이 되지 않은 노드끼리는 무한 비용이라고 작성한다. 

실제 코드 작성에서는 1e9, 99999999999 등의 값으로 초기화 하는 경우가 많다. 

INF = 1e9 

graph = [ 
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]

 

• 인접 리스트 (Adjacency List): 리스트로 그래프 여결 관계 표현 

인접 행렬로 저장하는 방식은 익숙했으나, 인접 리스트는 생각보다 익숙하지가 않은 표현 방식이다. 

graph = [[] for _ in range(3)]

graph[0].append((1, 7))
graph[0].append((2, 5))

graph[1].append((0, 7))


graph[2].append((0, 5))

#연결이 안된 노드는 아예 리스트에 포함시키지 않는다.

인접 리스트 방식이 메모리 소비가 적다. 다만 그만큼 인접 행렬이 연결 관계 정보를 얻기 더 쉽다. 다만 실제 현실 문제에서는 주로 sparse matrix 를 사용한다. 

DFS

깊이우선 탐색, 그래프의 깊은 부분은 우선적으로 탐색하는 알고리즘 

 

사실 해당 부분은 시각화 자료를 참고하는 것이 좋지만, 시각 자료를 가져다 놓는건 저작권 위반일 듯 하여, 말로 풀어서 표현해본다. 

 

1) 한 노드에서 시작한다. 

2) 해당 노드에서 간선으로 연결된 노드 중 가장 작은 노드로 이동한다. (방문한 노드는 stack에 넣고 방문한 노드는 방문 처리한다.)

3) 가장 작은 노드에서 또 가장 작은 노드로 이동한다. 

4) 더 이동할 곳이 없을 때는 바로 전에 방문했던 노드를 stack에서 꺼낸다. 

5) stack에서 꺼낸 노드에서 갈 수 있는 노드가 있으면 이동하고 이동이 불가능하면 다시 4번을 수행한다. 

6) 4,5 번을 반복 수행하면서 모든 노드를 방문한다. 

7) 모든 노드를 방문하고 나면 stack의 남은 원소를 빼낸다. 

 

소스 코드 구현은 다음과 같다. 

연결 관계 

1 - 2 - 3 - 8 

2 - 1 - 7 

3 - 1, 4, 5 

4 - 3, 5

5 - 3, 4 

6 - 7

7 - 2, 6, 8

8 - 1, 7

stack = []
graph = [
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
# dictionary 로 구현해도 좋을 것 같다. 

#just in case 
#to pop the smallest
graph  = [sorted(i) for i in graph]
visited = [0] * 8 

def dfs():
    tmp = stack.pop()
    print(tmp)
    visited[tmp-1] = 1
    for i in graph[tmp-1]:
        if visited[i-1] != 1:
            stack.append(i)
            dfs()

stack.append(1)
dfs()

문제 제시와 같이 graph 에서 더 작은 노드를 먼저 방문할 수 있도록 graph 를 한번 정렬해주었다. 

 

정답을 살펴보니 재귀로 동작하는 함수 특성상 이미 stack 이므로, stack 을 또다시 구현해줄 필요가 없다. 

def dfs(graph, i, visited):
    print(i)
    visited[i-1] = True
    for n in graph[i-1]:
        if not visited[n-1]:
            dfs(graph ,n, visited)

dfs(graph, 1, visited)

좀 더 짧게 구현이 가능하다. 

 

visited[i-1] = True 가 아니라 1 로 적어도 무방 

if not 으로 굳이 안해도 되지만 readability 가 높다. 

 

정리하자면 깊이 우선 탐색한다는 아이디어 자체가 처음 노드를 기준으로 일단 쭉쭉쭉 들어가야 한다. 

즉, stack 구조를 사용하여 가장 최근에 넣었던 node 를 타고 타고 들어간다. 

깊이 즉 stack 이다. 

BFS

너비 우선 탐색, 즉 가까운 노드부터 탐색하는 알고리즘이다. 

1) 첫 노드를 queue 에 넣는다. 

2) queue 에 들어있는 노드들을 우선적으로 모두 방문한다. (방문할 때 visited = True)

3) 노드들을 각각 방문할 때 마다 연결된 노드들을 queue 에 넣는다. 

4) 어차피 queue 는 처음 넣은 것이 먼저 방문되므로 거리낌없이 queue 에 넣어도 된다. 

5) 모두 방문하면 queue 에 남은 것 출력하고 종료 

 

from collections import deque 

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


queue = deque()
visited = [0] * 8 

start = 1
visited[start -1] = True

def bfs(graph, start ,visited):
    queue = deque([start])
    while(queue):
        tmp = queue.popleft()
        print(tmp)
        for i in graph[tmp-1]:
            if not visited[i-1]:
                visited[i-1] = True
                queue.append(i)
        


bfs(graph, start, visited)

유의할 점이라면 visitied = True 를 popleft 한 직후에 넣으면 너무 늦는다. 

queue pop left 되기 전까지는 방문 되지 않은 노드로 처리되어 for 문을 돌며 방문하지 않은 노드들을 추가할 때 같이 추가될 염려가 있다. 

 

BFS 도 재귀적으로 구현은 가능하다. 

from collections import deque 



def bfs(graph, visited):
    
    if len(queue) == 0 :
        return 

    tmp = queue.popleft()
    print(tmp)
    for i in graph[tmp-1]:
        if not visited[i-1]:
            queue.append(i)
            visited[i-1] = 1

    bfs(graph, visited)

start = 1
visited[start-1] = True
queue = deque([start])

bfs(graph ,visited)

그러나 재귀적으로 하는게 얼마나 어리석은지에 대해 다음글에서 논의가 되어있다. 

https://stackoverflow.com/questions/2549541/performing-breadth-first-search-recursively

Performing Breadth First Search recursively

 

1) 음료수 얼려먹기 

N X M 얼음 틀, 구멍이 뚫린 부분은 0, 칸막히 부분은 1이다. 상하좌우로 붙은 경우 연결된 것이다. 

 

import sys
input = sys.stdin.readline

row, column = map(int, input().split())
ice = []

for i in range(row):
    ice.append(list(map(int, input().rstrip())))
#.split()을 쓰면 0011 에서 00 이 사라지는 불상사가 존재 

#[int(e) for e in '0011'.rstrip()]
#list(map(int, list(input())))


dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
cnt = 0

def dfs():
    y,x = stack.pop()
    for i in range(4):
        if y + dy[i] < 0 or x + dx[i] < 0 or y +dy[i] > row-1 or x + dx[i] > column-1:
            continue
        if not ice[y+dy[i]][x+dx[i]]:
            ice[y+dy[i]][x+dx[i]] = 1
            stack.append((y+dy[i], x+dx[i]))
            dfs()
    

for i in range(row):
    for j in range(column):
        if ice[i][j] == 0:
            ice[i][j] = 1 
            stack = []
            stack.append((i,j))
            dfs()
            cnt += 1


print("answer", cnt)

 

stdin.readline 은 '\n' 까지 읽어온다. 만약 input 이 띄어쓰기로 구분 된 경우 편하게 split() 하면 '\n' 까지 자동으로 탈락되지만 지금과 같이 input이 '00111' 이런식으로 들어왔을 때 split을 쓰면 00이 탈락된다. 

 

이럴 때는 .rstrip() 으로 '\n' 만 탈락시킨다. 

 

나는 stack을 사용했으나, 정답지문에서는 stack을 사용하지 않는다. 

내가 stack을 왜 사용했는가 잘 살펴보니 다음의 두가지 문제가 있었다.

 

1) dfs 를 콜할 때 x,y 좌표를 보내주면 된다는 점 

2) 재귀 자체가 stack으로 동작한다는 점을 활용하지 않는다는 점

을 활용하지 않았다. 

즉, 재귀를 하는 이유가 stack 연산 필요없이 동작하도록 하는 건데, 나는 stack과 재귀를 둘다 쓰고 있었다. 

 

해당 부분을 생략하니 

import sys
input = sys.stdin.readline

row, column = map(int, input().split())
ice = []

for i in range(row):
    ice.append(list(map(int, input().rstrip())))

dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
cnt = 0

def dfs(i,j):
    y,x = i, j
    for i in range(4):
        if y <= -1 or x <= -1 or y >= row or x >= column:
            continue
        if not ice[y+dy[i]][x+dx[i]]:
            ice[y+dy[i]][x+dx[i]] = 1
            dfs(y+dy[i],x+dx[i])
    

for i in range(row):
    for j in range(column):
        if ice[i][j] == 0:
            ice[i][j] = 1 
            dfs(i,j)
            cnt += 1


print("answer", cnt)

y+dy[i] < 0 은 y = 1 dy[i] = -1 인 경우를 잘 반영하지만, y가 -1 dy[i] 1 인 경우도 가능하다는 논리로 이어질 수 있다. 

이에 따라 if y <= -1 or x <= -1 or y >= row or x >= column 이 맞다. 

위 알고리즘이 문제를 일으키지 않은건 운이 좋았다. 

어차피 첫 start 가 -1 이 아니므로 y + dy[i] < 0 만 만족하면 충분하다. 

 

그 외에는 좋다. 

여기서 주요했던건, 한 matrix 에서 dfs 를 여러번 시행해야 하는데, 그 부분을 놓치지 않고 잘 잡은 부분이다. 

 

 

2) 미로 탈출

N X M 미로에 갇혔다. 현재 위치는 (1,1) 이고 미로의 출구는 (N,M) 에 위치한다. 괴물이 있는 부분은 0, 없는 부분은 1 이다. 괴물을 피해 최소거리로 탈출하자. 

 

#BFS 최단거리 문제 
import sys
input = sys.stdin.readline
from collections import deque
row, column = map(int, input().split())

maze = []
queue = deque([(0,0)])
for i in range(row):
    maze.append(list(map(int, input().rstrip())))

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

maze[0][0] = 2


while(queue):
    y,x = queue.popleft()
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if nx == column-1 and ny == row-1:
            print(maze[y][x])
            exit()
        if nx < 0 or ny < 0 or nx > column-1 or ny > row-1:
            continue 
        if maze[ny][nx] == 0:
            continue
        elif maze[ny][nx] == 1:
            #print("maze[y][x]", maze[y][x])
            maze[ny][nx] = maze[y][x] + 1
            queue.append((ny, nx))

 

최단 거리를 찾는 문제이다. 

BFS 는 기본적으로 가장 가까운 node 들로 모든 경우를 살피며 한개씩 나아가다보니, 항상 특정 위치에 도착하는 최단 거리를 구하는 것이 가능하다. 

해당 문제에서 count 라는 변수를 하나 놓고 최단 거리를 구하려 했는데, 변수를 한개 사용하게 되면 BFS 에 의해 최단거리에 속하지 않는 노드들을 방문하는 경우도 같이 count 된다. 해당 상황들을 예외처리 해주는 작업은 복잡하다. 

이에 따라 visit 행렬을 만들어야 하는 경우도 있지만, 이건 메모리 공간을 차지한다. 

이에 따라 최적의 방법은 기존 미로 행렬을 활용하여 행렬 상에 기록을 하는 것이다. 특정 노드에서 여러 갈래로 뻗어나가더라도 각 여러 갈래는 전 노드의 값을 참고하여 +1 만 하면 되므로 구현도 간단하고 이해도 간단하다. 

 

알고리즘 문제에 따라 DFS, BFS 선정 기준 

https://foameraserblue.tistory.com/188?category=481823 

PS를 하며 느끼는 DFS와 BFS 선택의 기준

위 글에서 발췌한 내용이다. 

 

"내 개인적인 경험으로(나는 DFS를 더 자주 사용한다) 대부분의 경우 DFS와 BFS 어느것을 선택해도 무방한 문제들이 많다. (필자가 경험한 코딩테스트 수준의 알고리즘)

나는 보통 DFS는 재귀적인 특징과 백트래킹을 이용한, 모든 경우를 하나하나 전부 탐색하는 완전탐색 문제를 풀때 선호하고(대표적으로 조합 순열 구현)
BFS는 depth(깊이)특징을 이용한 문제(대표적으로 최단경로)를 풀어야할때 선호한다."

 

문제들을 풀면서 이해한 결과 BFS 는 한칸씩 나아갈 때 dx = [1, -1, 0, 0], dy = [0, 0, 1, -1] 을 모두 방문해야만 한다. 하지만 DFS 는 모든 것을 탐색하지 않고 우선 깊이 내려가므로 BFS 보다 상당히 효율적으로 보인다. 

(추가 내용 DFS 가 stack 구조를 사용해서 오히려 시간이 더 소요된다고 합니다.)

다만 DFS 는 최단 거리를 찾기에 용이하지 않다. 깊이 우선 탐색을 하는 과정에서 특정 노드에 도착하는 거리가 최단 거리가 아닐 수 있고, 이때 node 는 이미 방문한 노드로 취급되어 특정 노드에 도착하는 최단 거리를 구하기 위해서는 알고리즘을 복잡하게 짜야한다.