[플레이데이터][알고리즘] 깊이우선탐색(DFS) & 너비우선탐색(BFS)
깊이우선탐색(DFS) & 너비우선탐색(BFS)
🔊 2021.04.08 (목) 엔코아 플레이데이터 알고리즘 특강 3주차 내용을 정리한 노트 게시물입니다.
깊이우선탐색과 너비우선탐색을 보기 전에 스택과 큐를 먼저 알고 와야한다!
(참고: [플레이데이터][자료구조] 스택 & 큐)
PART 1. 깊이우선탐색(DFS)
깊이우선탐색(DFS)란?
Depth First Search의 약자로 넓이 우선 탐색을 의미
하나의 경우의 수에 대하여 모든 경우의 수를 조사하고 다음 경우의 수를 조사하면서 해를 찾는 과정
깊이우선탐색(DFS)의 구조
여기 하나의 트리구조가 있다고 생각해보자.
그럼 시작점인 A에서부터 정답을 찾아가는 과정을 살펴보도록 하자.
먼저 A가 정답인지 아닌지를 검사한다. 정답이 아니므로 우리는 A 아래에 있는 B, C, D를 검사해야하는데 우선 B부터 검사하도록 한다.
B도 정답이 아니다. 그러면 이제 C를 검사하면 될까? 아니다.
깊이우선탐색은 일단 B를 끝까지 파헤쳐보는 것이다. B 아래에 E, F가 존재한다.
우리는 E부터 검사한다. E도 정답이 아니다. 그러면 F로 넘어갈까? 아니다.
E 아래를 끝까지 조사해야한다. 그래서 J를 검사한다. J는 정답이 아니면서 더 이상 아래에 자식이 존재하지 않는다. 그렇기 때문에 J는 여기서 탈락하게 되고, 다시 돌아나가서 F를 확인해보도록 한다. F 역시 정답이 아니다.
그럼, F 아래에는 K와 L이 있는데 K부터 검사해보도록 한다. 하지만, K도 역시 정답이 아니고 탈락.
L도 검사해보자. 하지만, 역시 정답이 아니므로 탈락한다. 우리는 이렇게 B의 검사가 모두 끝났다.
이제는 C를 검사해보도록 한다. C는 정답이 아니기 때문에 C 아래 G를 검사해본다. G도 정답이 아니다. G 아래를 검사해보도록 한다. 정답이다.
우리는 정답을 발견했으므로 알고리즘을 여기서 종료하면 될 것이다.
여기까지가 깊이우선탐색의 기본구조였다.
스택의 활용
지난 스택과 큐 강의에서 깊이우선탐색을 스택의 활용 예시로 말했었는데 그럼 이 개념을 어떻게 깊이우선탐색에 적용시킬 수 있는지 그 로직을 살펴보도록 한다.
깊이우선탐색(DFS)과 스택
우선 우리가 탐색해야할 트리가 여기 있다. 한쪽 방향에서만 접근이 가능한 스택도 있다. 그리고, 정답인지 아닌지 판단할 조건문을 하나 만들어두도록 한다.
시작점은 A 이므로 A부터 검사하도록 하겠다. A는 정답이 아니므로 A 아래 가능한 경우의 수를 모두 스택에 담도록 한다. B, C, D가 담긴 것을 우리는 볼 수 있다.
그리고, A는 검사가 끝났다. 그럼 스택에서 우리는 가장 위에있는 B를 꺼내서 검사하도록 한다.
하지만, B는 정답이 아니므로 B 아래에 존재하는 경우의 수 E와 F를 스택에 추가한다.
그리고 B를 검사를 종료한다.
검사가 종료되었다면 스택에서 가장 위에 있는 E를 꺼내와서 검사하도록 한다. 하지만, E역시 정답이 아니므로 E 아래 존재하는 J를 스택에 추가해준다. 그리고, E는 검사를 종료한다.
다시 스택에서 가장 위에있는 J를 꺼내와서 검사하도록 한다. 하지만, J 역시 정답이 아니고, J 아래에 존재하는 경우의 수가 더 이상 존재하지 않기 때문에 스택에 추가할 것이 없다.
이렇게 해서, J는 검사가 끝났고, 다시 처음으로 돌아가서 스택에서 가장 위에 있는 F를 꺼내오도록 한다. F는 정답이 아니다. F는 정답이 아니므로 F 아래 존재하는 K와 L을 스택에 추가하도록 한다.
그리고, F를 종료한다.
다시 스택에 가장 위에 있는 데이터인 K를 꺼내와서 검사하도록 한다.
K는 정답이 아니면서 아래 경우의 수를 스택에 추가하려고 하지만 K 아래에는 더이상 추가할 데이터가 없기 때문에 검사를 여기서 종료하도록 한다.
이번엔 스택의 가장 위에 있는 데이터 L을 검사하도록 한다. L을 꺼내온다.
L 역시 정답이 아니고 아래 데이터가 더이상 존재하지 않기 때문에 스택에 추가할 것이 없다. 따라서, L의 검사는 여기서 종료하도록 한다.
이렇게 우리는 B 아래에 있는 모든 경우의 수에 대한 탐색이 끝났다. 하지만, 정답을 찾지 못했다. 그렇지만, 여전히 스택 안에는 데이터가 존재하고 있기 때문에 스택을 계속해서 검사해주도록 한다. 이번엔 C를 검사해야되겠다.
C를 검사한다. C는 정답이 아니다. 그래서 C 아래에 있는 데이터 G를 스택에 추가하도록 한다. 그리고 C는 검사를 종료한다.
스택에서 가장 위에 있는 데이터 G를 꺼내서 검사하도록 한다.
G 역시 정답이 아니므로 G 아래의 데이터를 추가해주도록 한다. 그리고 G를 종료한다.
스택에서 가장 위에 있는 데이터 불러온다.
그리고 검사했더니 우리가 원하던 정답이다. 따라서 여기서 우리는 알고리즘을 종료하면 될 것이다.
여기까지 깊이우선탐색과 스택을 어떻게 같이 사용할 수 있는지 알아보았다. 그러나, 어떤 문제에서 어떻게 활용할 수 있을지 감이 오지 않을 것이다. 그래서, 예시문제를 하나 보면서 실전감각을 키울 수 있도록 한다.
깊이우선탐색(DFS) 구현
미로찾기
깊이우선탐색의 가장 대표적인 문제로는 미로찾기가 있다.
아래와 같은 미로를 깊이우선탐색과 스택을 활용해서 같이 풀어나가보도록 한다.
문제를 보면 위와 같다.
먼저, 미로를 지날 수 있는 길을 0, 지날 수 없는 길을 1로 표현해보도록 한다.
그리고, 문제를 풀기 위해서 편의상 인덱스도 쉽게 볼 수 있도록 나타내도록 한다.
그럼, 이 문제를 풀기 위해 우리는 스택을 선언해줘야 된다. 그래서 스택을 하나 선언해준다. 그리고 정답인지 아닌지를 검사할 수 있도록 조건문도 하나 추가해주도록 한다.
처음에 시작점이 [0,0] 부터 검사를 시작하도록 한다.
[0,0]의 좌표는 도착지점이 아니므로 [0,0]에서 이동할 수 있는 곳은 오른쪽으로 가는 [0,1] 한 군데 밖에 없다. 따라서 이동 가능한 곳의 좌표 [0,1]을 스택에 담아주도록 한다. 그리고, [0,0]의 검사를 종료하도록 한다.
스택에는 지금 데이터가 남아있기 때문에 우리는 계속해서 검사를 진행해야한다. 스택에서 가장 마지막에 있는 데이터 [0,1]을 꺼내와 검사하도록 한다.
[0,1]은 정답이 아니므로 [0,1]에서 움직일 수 있는 곳을 스택에 담아주도록 한다. [0,1]에서 바로 움직일 수 있는 곳인 [0,2]와 [1,1] 두 군데를 담아주도록 한다. 그리고 [0,1]을 종료한다.
현재 스택에서 가장 위에 있는 데이터인 [0,2]부터 꺼내서 검사해보도록 한다.
[0,2] 역시 도착지점이 아니므로 [0,2]에서 오른쪽으로 한 칸 움직인 [0,3]을 스택에 담고 검사를 종료한다.
다시 스택에서 데이터를 꺼내온다.
검사를 하지만 [0,3]은 정답이 아니므로 [0,3]에서 이동가능한 [0,4]의 좌표를 스택에 담고 종료한다.
다시 [0,4]를 스택에서 꺼내온다.
마찬가지로 정답은 아니고 오른쪽으로 갈 수 있는 [0,5]를 스택에 담아주도록 한다. 그리고 [0,4]의 검사를 종료한다.
다시 스택에 마지막으로 들어간 데이터인 [0,5]를 꺼내서 검사한다.
도착지점이 아니므로 이동할 수 있는 아래 방향으로 갈 수 있는 [1,5]를 스택에 담고 종료한다.
스택에서 마지막에 있는 데이터 [1,5]를 검사하지만 마찬가지로 정답이 아님. 아래로 가는 [2,5]를 스택에 담고 검사를 종료한다.
스택에서 마지막에 있는 데이터 [2,5] 다시 꺼내와서 검사하도록 한다.
이번에도 아래로 갈 수 있는 [3,5]를 스택에 담아주고 종료한다.
다시 [3,5]를 스택에서 꺼내온다. 검사를 하고 정답이 아니므로 [3,5]에서 갈 수 있는 위치를 검색해서 [3,4]를 스택에 담아주도록 한다. 그리고, 검사를 종료한다.
다시 스택의 가장 마지막에 있는 데이터 [3,4]를 꺼내서 검사한다.
[3,4]에서는 현재 왼쪽으로 갈 수 있다. 따라서, [3,3]을 스택에 담아주고 검사를 종료하도록 한다.
다시 스택에서 제일 위에 있는 데이터를 꺼내주도록 한다.
[3,3]에서 갈 수 있는 곳은 현재 [2,3] 밖에 없다. 그래서, [2,3]의 좌표를 스택에 담아주고 [3,3]을 종료한다.
우리는 이 과정을 계속해서 반복해야한다.
스택에서 제일 위에 있는 데이터 [2,3]을 꺼내온다.
그리고 검사를 하는데 정답이 아니므로 [2,3]에서 갈 수 있는 곳의 좌표를 스택에 담고 종료해야되는데… [2,3]에서는 더이상 갈 수 있는 곳이 없다. 그래서, 스택에 아무것도 추가할 수 없다. 검사를 종료한다.
하지만, 우리가 지금 정답을 찾은 것이 아니므로 우리는 검사를 계속해서 진행해야한다. 지금 스택의 가장 마지막에는 처음에 아까 담아두었던 [1,1]이 아직 남아있다.
다시 [1,1]로 돌아가서 검사를 계속 진행해보도록 한다.
[1,1]을 꺼내서 검사를 하지만 정답은 아니고 아래로 이동할 수 있기 때문에, 아래로 가는 [2,1]의 좌표를 스택에 담는다. 그리고 [1,1]을 종료한다.
스택의 마지막에서 다시 [2,1]을 꺼내서 검사하고 왼쪽으로 갈 수 있는 [2,0]을 담도록 한다.
그리고, 종료한다.
여기까지의 로직을 보면 아마 알고리즘 진행이 어떻게 되는지 예상할 수 있을 것이기 때문에 진행과정만 간단하게 계속 본다. (여기서 진행과정 이미지는 생략…)
마지막! [5,5]에 도착지점에 도달하였을 때는 조건문에 의해서 True를 반환하고 알고리즘이 종료될 것이다.
만약, 도달하지 못했다면 스택이 먼저 데이터를 가지고 있지 않으면서 반복문에서 빠져나가 False를 반환하게 될 것이다. 미로찾기는 이것으로 끝이다.
지금까지의 과정을 코드로 구현하기는 분명 처음에는 쉽지 않다.
그리고, 이 과정을 코드로 적어 놓으려면 몇 주일 정도 걸릴 수도 있다.
한번 방금 예시의 전체 코드의 90% 정도 되는 핵심 부분만 발췌해서 같이 보도록 하자.
깊이우선탐색(DFS) 예시코드
미로찾기
while len(stack) > 0: # 스택에 데이터가 있다면 계속해서 반복 실행하겠다
now = stack.pop() # 스택에서 가장 위에 있는 데이터를 꺼내와 현재위치를 나타낼 now라는 변수에 담아준다.
if now == dest: # now라고 하는 변수가 도착지점인지 아닌지를 검사한다.
return True # 도착지점이라면 True를 반환
# 여기부턴 방향 설정
x = now[1] # x는 미로에서 x축으로 왼쪽방향 오른쪽방향을 나타내는 변수
y = now[0]
# x가 현재위치라면 x-1은 왼쪽방향인데 그 왼쪽방향으로 이동했을 때 인덱스 값을 벗어나면 안될 것이다.
# 따라서, "x-1이 -1보다 크다면" 이라는 조건으로 동작한다.
if x-1 > -1: # (왼쪽방향)
# 왼쪽으로의 인덱스 값이 벗어나지 않는다면, 갈 수 있는 길인지 아닌지를 확인하는 조건문
if maps[y][x-1] == 0:
stack.append([y,x-1]) # 갈 수 있다면 스택에 담고,
maps[y][x-1] = 2 # 기존의 지도에서 0 이었던 값을 2로 바꿈으로써 '방문하였다'고 표시
# x+1은 오른쪽방향 마찬가지로 지도를 벗어나면 안되므로
# 인덱스가 맵의 크기를 벗어나는지 벗어나지 않는지 확인해준다.
if x+1 < hori: # (오른쪽방향)
# 왼쪽방향과 같은 구성
if maps[y][x+1] == 1:
stack.append([y,x+1])
maps[y][x+1] = 2 # 방문했음을 표시안해주면 컴퓨터는 왼쪽, 오른쪽 왔다갔다하는 무한 루프에 빠질 수 있음
# 그러므로, 꼭 방문여부 체크!
# (위쪽 방향)
if y-1 > -1:
if maps[y-1][x] == 1:
stack.append([y-1,x])
maps[y-1][x] = 2
# (아래쪽 방향)
if y+1 < verti:
if maps[y+1][x] == 1:
stack.append([y+1,x])
maps[y+1][x] = 2
return False # 그러나, 이러한 과정을 거쳤음에도 미로를 탈출할 수 없다면
# 스택에 데이터가 없게 되어 while문을 빠져나가 False를 반환하게 될 것이다.
PART 2. 너비우선탐색(BFS)
너비우선탐색(BFS)란?
Breadth First Search의 약자로 넓이 우선 탐색을 의미
하나의 경우의 수에 대한 다음 단계의 모든 경우의 수를 조사하면서 해를 찾는 과정
너비우선탐색(BFS)의 구조
너비우선탐색은 같은 레벨의 단계를 모두 검사하고 다음 레벨로 넘어가는 방법
따라서, A와 같은 수준의 레벨인 A를 검사하도록 한다. 정답이 1레벨에는 존재하지 않으므로 다음 레벨을 검사하도록 한다… 2레벨
위에서와 마찬가지로 하나씩 들춰보고 정답이 없으면 다음 레벨로 이동하면 된다.
B.. 정답 아님, C도 정답 아님, D도 정답이 아니다.
정답이 없으므로 우리는 다음 레벨로 넘어가도록 한다… 3레벨
E 정답 아니다. F 정답이 아니다…. 정답이 여기 있다.
따라서, 정답이 존재하므로 우리는 여기서 알고리즘을 종료하면 되겠다.
앞에서 깊이우선탐색은 스택과 활용이 되는 것을 우리는 보았다. 이번에는 너비우선탐색이 어떻게 큐와 활용이 될 수 있는지 살펴보도록 한다.
너비우선탐색(BFS)과 큐
여기 우리가 탐색해야 할 트리가 있다. 너비우선탐색을 구현할 큐도 선언한다. 그리고, 정답인지 아닌지를 검사할 조건문을 만들어 둔다.
처음에 A를 시작으로 검사한다. A 담아서 검사중이다. A는 정답이 아니다.
따라서, A 아래 존재하는 B, C, D 세 개의 데이터를 모두 큐에 담아주도록 한다.
그리고, A의 검사를 종료한다.
큐는 선입선출(FIFO)의 구조로 먼저 들어간 B부터 검사를 시작하도록 한다.
B는 정답이 아니다. 따라서, B 아래 존재하는 데이터 E, F를 큐에 담아주도록 한다.
그리고 B를 종료한다.
이번에는 큐에 넣었던 데이터 중에 가장 먼저 들어갔었던 C를 꺼내서 검사할 차례이다.
C는 정답이 아니므로, C 아래에 있는 데이터를 큐에 담아주고 C를 종료한다.
이번에는 D를 검사하도록 한다.
D는 정답이 아니므로 D 아래 존재하는 H와 I 두 개의 데이터를 큐에 담아주고 검사를 종료한다.
2레벨까지 검사가 끝났지만, 정답이 존재하지 않아 다음 레벨로 넘어가도록 한다. (표현이 다음 레벨이지만 별 다를 것 없이 계속 이 과정을 반복하는 것임)
현재 큐에 가장 먼저 들어갔던 데이터는 E 이다. 따라서, E를 꺼내 검사하고
E는 정답이 아니므로 E 아래에 있는 데이터 J를 큐에 담도록 한다.
E의 검사를 종료한다.
계속해서 큐에서 다음 데이터를 꺼낸다. 이번에 F가 나온다. F 역시 정답이 아니므로 F 아래에 있는 데이터 K와 L을 큐에 담고 검사를 종료한다.
다음 큐에서 데이터를 꺼내 검사를 진행한다.
우리가 원하는 정답이다! 따라서, 알고리즘을 여기서 종료한다.
지금까지는, 큐가 너비우선탐색과 어떻게 사용될 수 있는지를 알아보았다.
그러나 어떠한 문제에서 너비우선탐색을 적용시킬 수 있는지 그 구현 방법을 예제와 함께 보도록 한다.
너비우선탐색(BFS) 구현
최단경로찾기
주어진 문제를 풀기 위해서 우리는 큐를 선언하도록 한다. 그리고 데이터를 검사할 조건문도 만들어두도록 한다.
그럼 시작점인 1을 먼저 큐에 넣어두고 검사를 진행하도록 한다.
단, 주어진 문제를 풀 때 하나의 변수가 더 필요하다.
바로 큐에 있는 데이터들이 어디까지가 섬과의 거리가 1인지 2인지를 나타내줄 필요가 있기 때문이다.
이미지에 보이는 것처럼 ‘거리 0의 개수는 1개다’ 라고 표현을 했는데, 현재 큐에 포함된 데이터들이 1번 섬과의 거리를 가진 섬이 몇 개인가를 나타내는 변수이다.
현재 큐에 1번 섬이 1개만 들어있고, 1번 섬과 1번 섬의 거리는 0이기 때문에 ‘거리 0의 개수는 현재 1개다’라고 표현을 해놨다.
한번 검사 진행해보도록 한다.
큐에서 데이터를 꺼낸다.
그럼 거리가 0인 섬의 개수는 1이 아닌 이제 0이 된다.
그럼, 이제 다음에 들어올 데이터들은 거리가 1인 섬들이 되는 것이다.
현재 검사중인 1번 섬은 정답이 아니기 때문에 1번 섬과 연결된 2번, 5번, 6번을 큐에 추가해주도록 한다.
현재 3개의 섬이 추가되었기 때문에 이 3개의 섬들은 1번 섬과의 거리가 1이다. 그리고, 1번 섬 검사를 종료한다.
현재 큐에 가장 먼저 들어간 데이터 2부터 꺼내서 검사를 해보도록 한다.
2번이 꺼내지게 되면 큐에 거리가 1인 섬들의 개수는 2개로 줄어든다. 그리고, 2번 섬은 정답이 아니므로 2번과 연결된 3번과 11번을 큐에 추가해주도록 한다.
그리고, 2번 섬의 검사를 종료한다.
다시 큐의 제일 아래에 있는 5번 섬을 꺼내서 검사하도록 한다.
다시 거리 1의 개수가 하나 줄어들었다.
그리고, 5번 섬은 우리가 원하는 목적지가 아니므로 5번 섬과 연결된 9번과 11번 섬을 담아야 하는데, 11번 섬은 이미 담겨있다. 그렇기 때문에 우리는 9번 섬만 담도록 한다.
그리고 5번 섬의 검사를 종료한다.
이제 큐에서 6번 섬을 꺼내온다.
6번 섬을 마지막으로 6번 섬이 나옴에 따라서 큐에는 더이상 거리가 1인 섬들이 존재하지 않게 된다. 6번 섬과 연결된 섬인 3번과 12번이 있지만 3번은 이미 추가가 되었기 때문에 우리는 12번만 추가하도록 한다.
그리고, 거리가 1인 섬의 개수는 0이 되었기 때문에 큐에 존재하는 남은 섬들의 거리는 전부다 거리가 2인 섬들이다.
따라서, 거리가 2인 섬들의 수는 4로 바꾸어 주도록 한다.
그리고, 6번 섬의 검사를 종료한다.
계속해서 검사를 진행하도록 한다. 큐에 가장 먼저 들어왔던 데이터 3을 꺼내어 검사하도록 한다.
그리고 3번과 연결된 7번, 8번이 새롭게 큐에 추가된다.
그리고, 3번의 검사가 종료된다.
이번엔 11번 섬을 검사하도록 한다.
마찬가지로, 거리가 2인 섬의 개수는 하나 줄어들면서 11번과 연결된 섬인 8번을 추가하려고 하나 8번은 이미 추가 되었으므로 추가하지 않고, 검사를 종료하도록 한다.
이번엔 큐에 가장 먼저 들어갔었던 데이터 9번 섬이다.
9번 섬은 정답이 아니므로, 9번 섬과 연결된 10번 섬을 추가하고 검사를 종료한다.
큐에 가장 밑에 있는 데이터 12번을 꺼낸다.
12번은 우리가 원하던 정답이기 때문에 현재 거리인 2를 반환하면서 우리는 알고리즘을 종료할 것이다.
예시코드를 한번 보면서 마무리 하도록 한다.
너비우선탐색(BFS) 예시코드
최단경로찾기
# 깊이우선탐색과 마찬가지로 while문으로 큐가 빌 때까지 검사를 진행해준다.
while len(queue) > 0:
# count는 현재 큐에 있는 데이터의 개수를 얻어와서,
count = len(queue) # 저 갯수만큼 같은 거리에 있는 섬을 나타내고 있다
# 이 for 반복문은 count갯수 만큼 안에서 큐에서 데이터를 꺼내는 작업과 검사하는 작업이 진행되는 것
for time in range(count): # 그리고, for문이 끝나게 되면
now = queue.pop(0) # 같은 거리 섬이 0이 되면서 1번 섬과의 거리가 한 단이 더 증가하게 될 것이다.
if now == dest: # 여기 if문은 큐에서 추출한 데이터가 정답이면
return answer # 거리를 바로 반환하면서 알고리즘이 종료되도록 만듬
# 아래는 완전 탐색으로
for i in data: # 섬들 간의 연결 리스트들을 돌면서 방문하지 않은 연결된 섬들만 큐에 추가하도록 구성함
if i[0] == now and visited[i[1]-1] == False:
queue.append(i[1])
visited[i[1]-1] = True
elif i[1] == now and visited[i[0]-1] == False:
queue.append(i[0])
visited[i[0]-1] = True
# 하나의 for문이 끝났다는 것은 같은 거리의 섬들의 탐색이 끝났으므로
answer += 1 # answer에 1을 증가시켜 다음 레벨로 넘어가는.. 즉, 1번 섬과의 거리를 1 더 멀어지게 함
return answer
이번 주제인 깊이우선탐색과 너비우선탐색은 절대 쉬운 영역이 아니다.
문제가 변형됨에 따라 우리가 이 구조를 변경해서 활용할 줄 알아야 하기 때문에, 많은 문제를 접하면서 스스로 충분히 학습하자!
Leave a comment