DFS, BFS는 코딩테스트를 준비해봤다면 꼭 한 번 들어봤을 주제이고 실제로도 매우 자주 등장하는 유형이라고 한다. 그래프 자료구조의 탐색을 알고리즘으로 간단하게 말하면 원하는 데이터를 찾는 과정이다.
DFS, BFS를 살펴보기 전에 두 가지 자료구조에 대해서 살펴보아야 한다.
스택 자료구조
먼저 들어온 데이터가 나중에 나가는 형식(선입후출, First in Last out)의 자료구조이다. 쌓기나무나 접시쌓기를 생각하면 된다. 접시를 하나씩 쌓는다고 생각해보자. 그러고 나서 사용할 접시를 집으려고 하면 맨 위에 있는 즉, 가장 마지막에 쌓은 접시를 사용하게 된다. 맨 처음 들어온 접시는 위에 접시가 다 사용되기 전까지는 사용할 수 없다.
스택을 파이썬 코드로 표현하면 다음과 같다.
stack = []
stack.append(5)
stack.append(2)
stack.append(3)
stack.pop()
stack.append(1)
stack.pop()리스트 자료형을 활용하여 append, pop을 해주면 된다. 5, 2, 3을 넣어준 후에 pop을 하면 마지막 넣어준 3이 stack을 빠져나오게 된다. 그리고 append, pop은 모두 동작 시간이 상수 시간이기 때문에 스택은 시간적인 측면에서도 잘 사용하면 큰 이득을 볼 수 있는 자료구조이다.
Queue 자료구조
Queue는 스택과 반대로 먼저 들어온 데이터가 먼저 나가는(선입선출, First in First out)의 자료구조이다. 터널을 생각해보면 쉽다. 먼저 터널을 먼저 들어온 자동차가 먼저 터널을 통과해서 나가게 된다.
큐를 파이썬 코드로 표현하면 다음과 같다.
from collections import deque
queue = deque()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()collections 라이브러리에서 deque 라는 녀석을 가져와야한다.
처음에 deque()로 큐를 하나 만들어준 다음 스택과 같이 append를 통해서 아이템을 넣어주면 된다. 하지만 내보낼 때는 popleft를 활용하여 내보낸다. append를 하면 왼쪽부터 하나씩 추가되어 5, 2, 3, 7 이런 식으로 추가가 된다. 그러면 먼저 들어온 원소가 가장 왼쪽에 있으므로 popleft를 해서 2, 3, 7 이런 식으로 바뀌게 된다. append, popleft를 활용하여 큐 자료구조의 데이터 입력, 출력을 하면 된다.
재귀 함수
재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수이다. 재귀 함수를 사용할 때 가장 중요한 것은 종료 조건을 반드시 명시해야 한다는 것이다. 안 그러면 무한히 호출되어 터미널이 터지는 장면을 볼 수 있다.
재귀함수를 활용한 예제로는 피보나치가 가장 유명한 듯하지만, 여기서는 유클리드 호제법을 활용한 최대공약수를 계산해보려 한다.
두 수 A, B (A>B)가 있을 때 A를 B로 나눈 나머지를 R이라고 하자.
A,B의 최대공약수는 B와 R의 최대공약수와 같다는 것이 유클리드 호제법의 아이디어이다.
이를 코드로 구현하면
def gcd(a,b):
if a%b== 0:
return b
else :
return gcd(b,a%b)나누어 떨어지면 나누는 수가 최대공약수가 될 것이고 아니라면 나머지와 나누는 수에 대해서 함수를 재귀적으로 돌게 구성한 것이다.
재귀는 이처럼 잘 쓰면 매우 유용하지만 항상 종료 조건을 명시해야한다는 점, 그리고 잘못 쓰면 가독성이 떨어질 수 있다는 점을 유의해서 사용하면 된다.
DFS
위에서 배운 내용을 바탕으로 이제 DFS (Depth-First Search)에 대해 알아보자.
DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택 또는 재귀 함수를 이용하여 동작한다.
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 수행할 수 없을 때까지 반복한다.
(작은 순으로 인접 노드 선택한다고 가정)
1에서부터 시작 => 1 방문 처리
인접한 노드 2 스택에 추가 => 2 방문 처리
2에 인접한 노드 7 스택에 추가 => 7 방문 처리
7에 인접한 노드 6 스택에 추가 => 6 방문 처리
6 인접 노드 없으므로 => 스택에서 제거
7에 인접한 노드 8 스택에 추가 => 8 방문 처리
8 방문 처리 안된 인접 노드 없으므로 => 스택에서 제거
7 더이상 방문 처리 안된 인접 노드 없으므로 => 스택에서 제거
2 더이상 방문 처리 안된 인접 노드 없으므로 => 스택에서 제거
1에 인접한 노드 3 스택에 추가 => 3 방문 처리
3에 인접한 노드 4 스택에 추가 => 4 방문 처리
4에 인접한 노드 5 스택에 추가 => 5 방문 처리
5 더이상 방문 처리 안된 인접 노드 없으므로 => 스택에서 제거
4 더이상 방문 처리 안된 인접 노드 없으므로 => 스택에서 제거
3 더이상 방문 처리 안된 인접 노드 없으므로 => 스택에서 제거
1 더이상 방문 처리 안된 인접 노드 없으므로 => 스택에서 제거
탐색 완료
탐색 순서
1 -> 2 -> 7 -> 6 -> 8 -> 3 -> 4 -> 5
이를 코드로 구현하면 아래와 같다.
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False] * 9
def dfs(graph,v, visited):
visited[v] = True
print(v, end=" ")
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
dfs(graph,1, visited)노드는 보통 1번부터 시작하므로 graph에서 0번 인덱스를 비우고 1번부터 인접 노드를 작성했다. 방문 처리 위한 visited 역시 순서를 위하여 9개로 구성하였다.
처음 시작점 v를 넣어주면 시작 노드를 방문 처리 한다. 그 다음 인접 노드가 있는 리스트를 반복문으로 돌면서 방문하지 않으면 다시 그 노드에 대해서 DFS를 수행할 수 있도록 재귀적으로 코드를 구성했다. 만약 위에서 7번 노드 같은 경우가 i에 들어오면 6번 노드에 대해서 dfs를 수행한다. 하지만 이미 7은 visited가 True이기 때문에 반복문에서 할 게 없다. 그러면 v가 6인 dfs 함수는 스택에서 제거된다. 그 다음 7을 기준으로 수행했던 반복문에서 8번 노드에 대해서 dfs를 수행한다.
방문하지 않은게 있으면 그걸 기준으로 계속 깊이 내려가기 때문에 Depth First Search, 깊이 우선 탐색이라고 한다.
BFS
BFS (Breadth-First Search)는 너비 우선 탐색이라고 부르며 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. BFS는 큐 자료구조를 사용하고 동작과정은 다음과 같다.
1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리한다.
3. 2번의 과정을 수행할 수 없을 때까지 반복한다.
1번 노드 방문 처리 후 큐에 삽입 => 1
1번 노드 큐에서 꺼낸 후 인접한 2번, 3번, 8번 노드 방문 처리 후 큐에 삽입 => 2,3,8
2번 노드 큐에서 꺼낸 후 인접한 7번 노드 방문 처리 후 큐에 삽입 => 3, 8, 7
3번 노드 큐에서 꺼낸 후 인접한 4번, 5번 노드 방문 처리 후 큐에 삽입 => 8, 7, 4, 5
8번 노드 큐에서 꺼낸 후 방문 처리 안된 인접 노드 없으므로 그대로 진행 => 7, 4 ,5
7번 노드 큐에서 꺼낸 후 인접한 6번 노드 방문 처리 후에 큐에 삽입 => 4, 5, 6
4번 노드 큐에서 꺼낸 후 방문 처리 안된 인접 노드 없으므로 그대로 진행 => 5, 6
5번 노드 큐에서 꺼낸 후 방문 처리 안된 인접 노드 없으므로 그대로 진행 => 6
6번 노드 큐에서 꺼낸 후 방문 처리 안된 인접 노드 없으므로 그대로 진행 => empty
탐색 완료
탐색 순서
1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6
이를 코드로 구현하면 아래와 같다.
graph = [
[],
[2,3,8],
[1,7],
[1,4,5],
[3,5],
[3,4],
[7],
[2,6,8],
[1,7]
]
visited = [False] * 9
from collections import deque
def bfs(graph, start, visited):
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
bfs(graph,1, visited)DFS와 마찬가지로 그래프와 방문 기록을 확인하는 리스트를 만든다.
처음 큐에 시작점을 넣어준 상태로 선언해주고 시작점의 방문 처리를 완료해준다. 큐에 있는 모든 원소를 다 탐색할 때까지 반복문을 도는데 먼저 큐에서 popleft를 해준 후 인접 노드의 방문 여부를 확인 후 방문을 안했다면 방문 처리를 해준 후 큐에 넣어준다. 그 다음에 계속 큐의 첫번째 원소 제거한 후 방문 처리 안된 인접 노드 큐에 추가, 없으면 첫번째 원소만 제거된 후 종료된다.
층별 인접 노드들을 전부 다 살피기 때문에 깊이가 아니라 층별로 즉, Breath First Search 너비 우선 탐색이라고 부른다.
예제)
2차원 배열에서 탐색을 하는 문제이다. 이는 2차원 배열을 전부 다 반복문으로 돌면서 DFS로 확인해야 하는 문제이다.
시작점인 [0,0]에서부터 인접한 노드들의 탐색을 시작한다. 그리고 탐색을 완료할 경우 1로 값을 변경하여 다시 탐색하지 않게 한다. [0,0]의 값을 1로 바꾸고 상하좌우 4개의 노드를 하나씩 살핀다. [0,1] 노드에 대해서 탐색을 시작하면 값을 1로 변경한 후에 다시 상하좌우 노드를 다 탐색한다. 위로 가면 틀을 벗어나고 좌우에 있는 노드들은 값이 1이므로 더이상 탐색할 필요가 없다. 그래서 아래쪽에 있는 [1,1] 노드만 탐색을 하고 값을 1로 변경한 후에 다시 그 노드를 기준 상하좌우를 탐색한다. 만약에 주변이 모두 1로 둘러쌓여있다면 이는 아이스크림의 경계선에 닿은 것이므로 덩어리 하나를 완성시킨 것이다.
이를 코드로 나타내면 다음과 같다.
n,m = map(int,input().split(" "))
graph= []
for i in range(n):
graph.append(list(map(int, input())))
result = 0
def dfs(x,y):
if x<=-1 or x>=n or y<=-1 or y>=m:
return False
if graph[x][y] == 0:
graph[x][y]=1
dfs(x-1, y)
dfs(x+1,y)
dfs(x,y-1)
dfs(x,y+1)
return True
return False
for i in range(n):
for j in range(m):
if dfs(i,j) == True:
result+=1
print(result)dfs 안의 코드는 틀을 벗어날 경우 False를 리턴하고 값이 0일 경우 아이스크림이 생성될 수 있으므로 방문 처리를 한 후에 주변에 있는 노드들 중에서 0이 또 있는지 없는지 확인하는 것이다. 만약 값이 1인 노드라면 False를 리턴하고 탐색을 종료시켜버린다. 그래서 상하좌우가 다 1로 둘러쌓여있으면 더이상 탐색을 하지 못하고 모든 스택의 dfs를 처리한 후 True를 리턴하여 아이스크림의 개수를 1개 늘린다.
근본적인 생각은 0이 발견되면 일단 무조건 아이스크림이 된다는 점, 그리고 어디까지 확장할 수 있는 확인하기 위하여 주변의 모든 노드를 탐색해야하고 그 방법이 재귀를 활용한 DFS였다는 점이다.
예제)
마찬가지로 주변에 가능한 길이 있는지 없는지를 탐색해야 한다. 하지만 여기서는 여부가 아니라 움직인 정도를 측정하고 싶은 것이다. 이 때는 BFS를 활용하면 된다. 즉 Breath가 총 몇단계로 내려가는 지를 확인하는 과정이다.
시작점에서 출발한 후 그 다음에 가능한 길들은 모두 2만큼 움직여야한다. 그다음은 3, 4, 5, 6 ... 이런식으로 그 지점까지 가기 위해 움직인 거리를 모든 1값이 있는 노드들에 대해서 취해주면 된다.
from collections import deque
n,m = map(int, input().split(" "))
graph = []
for i in range(n):
graph.append(list(map(int,input())))
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs(x,y):
queue = deque()
queue.append((x,y))
while queue:
print(queue)
x,y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx<0 or nx>=n or ny<0 or ny>=m:
continue
if graph[nx][ny] == 0:
continue
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx,ny))
print(graph)
return graph[n-1][m-1]여기서도 상하좌우를 판단해주나 방법이 위의 예제에서 일일이 해준 것과 별개로 방향벡터를 사용했다.
판에서 벗어나거나 0 이 있으면 나아가질 못하므로 continue로 코드를 작성했다.
좌표의 값을 큐에 입출력해주는 방식으로 탐색을 한다.
[0,0] 노드에서 출발하여 [1,0] 노드에 2 값을 대입한 후 상하좌우를 다 탐색한다.
이 때 [0,0] 노드도 다시 탐색하게 되어 값이 2+1=3이 되고 [1,1] 노드도 값이 3으로 변경된다.
그 다음 [0,0] 노드에 대해서 for 문을 돌면 해당하는 내용이 하나도 없으므로 큐에서 나오기만 한다.
-> 출발점이 거리가 움직인 거리가 3이라는 게 버그라고 볼 수 있다.
[1,1] 노드에 대해서 인접한 노드의 거리를 또 키우고 그 다음 인접한 노드의 좌표를 큐에 추가한다.
이런 식으로 계속 하다보면 모든 1에 대해서 움직인 거리가 얼마인지 나온다. 하지만 우리는 맨 우측 하단 좌표까지 움직인 거리만 알면 되므로 모든 탐색을 마친 후의 [n-1, m-1]의 값을 리턴해주면 된다.
이름은 너비 우선 탐색이었지만 실제로 얼마나 깊게 탐색을 해야하는지 측정할 수 있었다. 한층한층 모든 탐색을 진행하다보니 오히려 움직인 거리와 같이 계층의 깊이를 나타낼 수 있는 부분을 구하는 문제는 BFS를 사용하는 것이 더 좋을 듯하다.
DFS, BFS는 한 번만 봐서는 완벽하게 이해하기가 정말 어려운 것 같다. 꾸준한 반복 학습 그리고 DFS가 스택 자료구조를 어떻게 사용하는지, BFS가 큐 자료구조를 어떻게 사용하는지 그 코드를 거의 외우다시피 하는 것이 좋을 것 같다.
'스터디 > 코딩테스트' 카테고리의 다른 글
| python 코딩테스트 - 프로세스 (0) | 2023.11.05 |
|---|---|
| python 코딩테스트 - 완주하지 못한 선수 (0) | 2023.11.05 |
| python 코딩테스트 - 체육복 (2) | 2023.11.02 |
| python 코딩테스트 - 그리디, 구현 (3) | 2023.11.02 |
| javascript 코딩테스트 - 요격 시스템 (0) | 2023.09.20 |