우리는 길을 찾을 때 보통 지도를 들고 시작점부터 끝점까지 갈 수 있는 방법들을 대략적으로 그린 뒤, 그 중 기준에 따라서 시간이 제일 짧게 걸리거나, 거리가 제일 짧은 경로를 선택해서 가곤 한다. 그런데 컴퓨터는 바보라서 지도를 전체적으로 볼 수도 없고, “대략적인 경로”라는 걸 직접 가보기 전에는 생각해낼 수가 없다. 컴퓨터는 무조건 어떤 좌표를 주면 눈 앞에 있는 것밖에 보지 못하기 때문이다. 마치 정원 미로에 들어간 사람처럼…
하지만 우리가 생각해내기 귀찮은 아주 반복적인 작업을 빠르게 잘하는 컴퓨터는, 모든 경로를 우리 눈 보다 빠르게 뒤져보고 우리보다 빨리 정답 경로를 찾아낼 수 있다. 그래서 눈앞에 주어진 정보만으로 주어진 지도의 모든 경로를 뒤져보는 알고리즘을 트리순회(Tree Traverse, 줄이면 ㅜㅜ) 알고리즘이라고 부른다.
이 트리 순회는 정말 많은 알고리즘들이 있다. 간단한 DFS, BFS부터 시작해서 Parameter가 주어지는 다익스트라 알고리즘, 그리고 스타크래프트에도 들어있고 그럴듯한 길찾기 인공지능의 시작점인 A*(A star) 알고리즘 등 경우에 따라서 정말 많은 알고리즘들이 쓰이고 있다. 그 중에 이 글에서는 DFS와 BFS란 걸 다뤄보려 한다.
DFS는 이름에 써있듯이 처음 시작점에서 방향을 정해 출발하면 그 방향으로 쭉 가본 다음에 갈 수 없으면 안가본 길을 차근차근 찾는 방식의 순회 방법이다. 예를 들어 트리가 아래처럼 생겼다면
1번부터 시작해서 2번 → 4번 → 5번 → 3번 순서대로 순회를 하게 된다. 앞에서 말했던 미로에 빗대어 얘기해보면, 컴퓨터는 일단 1번 위치에서 2번하고 3번을 눈앞에 보게 된다. 여기서 순서는 상관 없지만 작은 숫자 먼저 간다고 생각하면, 3번을 “아직 안간 곳 리스트” 메모해두고 2번으로 가면서 1번은 “이미 간 곳 리스트”에다가 기록을 한다. 그럼 이제 컴퓨터는 눈앞에 4번과 5번을 보게 되는데, 여기서 다시 작은 숫자인 4번으로 가면 3번을 메모한 메모지 옆에 5번을 쓰고 2번은 이미 간 곳으로 처리한다. 그러면 안 간 곳에 3번과 5번이 써있는데, 가장 최근에 써넣은 곳부터 방문한다고 하면 5번과 3번을 차례대로 방문하게 되고 위의 그림처럼 그래프 위의 모든 점들을 한 번씩 가보게 된다.
알고리즘스럽게 DFS로 그래프를 순회하는 법을 정리하면 이렇게 된다.
- 현재 위치와 인접한, 아직 가보지 않은 곳을 스택에 저장해 기록
- 스택에서 하나를 꺼내 현재 위치를 꺼낸 위치로 다시 설정
- 현재 위치를 이미 간 곳으로 표시한 뒤 스택이 빌 때까지 1, 2, 3 순서대로 반복
코드로 그래프 객체와 DFS 알고리즘을 구현하면 이렇게 할 수 있다.
const graph = [
[], // 0번 노드는 없으므로 빈 배열
[3, 2], // 1번 노드의 자식 노드들
[5, 4], // 2번 노드의 자식 노드들
[], // 3번 노드의 자식
[], // 4번 노드의 자식
[] // 5번 너 이 자식
]
function dfs(graph, startNode) {
// 아직 안간 곳 체크하는 스택
const stack = []
// 이미 간 곳들 체크하는 배열(안갔으니 false로 초기화)
const visited = new Array(graph.length).fill(false)
// 처음 시작 지점 스택에 저장
stack.push(startNode)
let current // 그래프에서 현재 위치
const traversePath = []
// 스택이 빌 때까지(=안간 곳이 없을 때까지)
while (stack.length) {
current = stack.pop()
// 현재 위치를 경로에 저장
traversePath.push(current)
// 최근 위치를 간 곳으로 표시
visited[current] = true
// 현재 위치에서 보이는 노드들에 대해서
for (let child of graph[current]) {
// 아직 안가본 곳이라면
if (!visited[child]) {
stack.push(child) // 스택에 저장
}
}
}
return traversePath
}
console.log(dfs(graph, 1)) // 결과 : [1, 2, 4, 5, 3]
이렇게 stack과 visited를 만들고 시작 위치로 초기화한 다음에 stack에서 하나씩 pop 해가면서 주변에 안 간 곳들을 stack에 넣으면 그래프의 모든 곳들을 한 번씩 순회하는 코드를 만들어낼 수 있다.
그런데 그래프를 순회할 수 있는걸로 뭘 할 수 있는데? 라는 궁금증이 생길 수 있다. 우리가 코테 공부하면서 제일 많이 볼 수 있는 예시를 들면, 지도에서 특정한 지점과 연결되어있는 영역의 크기를 구할 때 굉장히 유용하게 사용할 수 있다.
"이것이 취업을 위한 코딩 테스트다"(줄여서 이코테)에 있는 간단한 문제중에 하나이다. 0은 음료수를 부을 수 있는 곳이고 이렇게 음료수를 부으면 붙어있는 0끼리는 하나의 얼음덩어리가 돼서, 만들 수 있는 얼음덩어리 개수를 세는 문제로, DFS를 이용해서 풀면 아래 코드처럼 풀 수 있다.
function solution(N, M, iceTray) {
let res = 0 // 전체 얼음 개수
for (let x = 0; x < M; x++) {
for (let y = 0; y < N; y++) {
if (iceTray[y][x] === 0) {
iceTray = freezeSoda(N, M, iceTray, x, y)
res++
}
}
}
return res
}
// (x, y) 위치를 받아 해당 위치에서 인접한 0들을 모두 1로 바꿈(얼려버림)
function freezeSoda(N, M, iceTray, x, y) {
// 순서대로 아래, 위, 왼쪽, 오른쪽
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
const stack = []
// 2차원 배열로 선언!
const visited = Array.from(Array(M), () => new Array(N).fill(false))
// 처음 시작 지점 스택에 저장
stack.push([x, y])
let current // 그래프에서 현재 위치
while (stack.length) {
current = stack.pop()
const [curX, curY] = current
// 현재 위치를 0에서 1로 바꿔 얼려버림
iceTray[curY][curX] = 1
// 최근 위치를 간 곳으로 표시
visited[curY][curX] = true
// 현재 위치에서 보이는 위/아래/왼쪽/오른쪽 4방향에 대해서
for (let i = 0; i < 4; i++) {
// 다음 위치 설정
const nextX = curX + dx[i]
const nextY = curY + dy[i]
// 만약 다음 위치가 갈 수 없는 곳이면 무시
if (nextX < 0 || nextX >= M || nextY < 0 || nextY >= N) continue
// 만약 다음 위치가 벽이라면(1이라면) 무시
if (iceTray[nextY][nextX] === 1) continue
// 아직 가지 않은 곳이라면
if (!visited[nextY][nextX]) {
stack.push([nextX, nextY]) // 스택에 저장
}
}
}
return iceTray // 한 구역 얼린 뒤의 얼음판 반환
}
const N = 4 // 세로 길이
const M = 5 // 가로 길이
const iceTray = [ // 얼음 틀
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 1],
[1, 1, 1, 1, 1],
[0, 0, 0, 0, 0]
]
console.log(solution(N, M, iceTray)) // 결과 : 3
이렇게 인접한 영역들을 동적으로 확인하고 계산할 때 많이 쓸 수 있다. 이 외에도 다양한 활용 방식이 있으나 BFS를 먼저 살펴보자.
BFS는 DFS와는 조금 다르게 그래프의 노드를 모두 한 번씩 순회하는 방식으로, 그림으로 보면 아래와 같다.
먼저 1번에서 보이는 2, 3번을 순서대로 간 다음에, 2번의 자식 노드들을 또 차례대로 거쳐간다. DFS 코드를 한 번 짜보면 BFS는 쉽게 짤 수 있는데, DFS에서 스택으로 썼던걸 큐로 바꿔주기만 하면 되기 때문이다. 아래의 BFS 코드와 위의 DFS 코드를 비교해보면 확인할 수 있다.
const graph = [
[], // 0번 노드는 없으므로 빈 배열
[2, 3], // 1번 노드의 자식 노드들
[4, 5], // 2번 노드의 자식 노드들
[], // 3번 노드의 자식
[], // 4번 노드의 자식
[] // 5번 너 이 자식
]
function bfs(graph, startNode) {
// 아직 안간 곳 체크하는 큐
const queue = []
// 이미 간 곳들 체크하는 배열(안갔으니 false로 초기화)
const visited = new Array(graph.length).fill(false)
// 처음 시작 지점 큐에 저장
queue.push(startNode)
let current // 그래프에서 현재 위치
const traversePath = []
// 큐가 빌 때까지(=안간 곳이 없을 때까지)
while (queue.length) {
current = queue.shift()
// 현재 위치를 경로에 저장
traversePath.push(current)
// 최근 위치를 간 곳으로 표시
visited[current] = true
// 현재 위치에서 보이는 노드들에 대해서
for (let child of graph[current]) {
// 아직 안가본 곳이라면
if (!visited[child]) {
queue.push(child) // 큐에 저장
}
}
}
return traversePath
}
console.log(bfs(graph, 1)) // 결과 : [1, 2, 3, 4, 5]
마찬가지로 얼려먹는 문제도 풀어보면 아래 코드처럼 풀 수 있다.
function solution(N, M, iceTray) {
let res = 0 // 전체 얼음 개수
for (let x = 0; x < M; x++) {
for (let y = 0; y < N; y++) {
if (iceTray[y][x] === 0) {
iceTray = freezeSoda(N, M, iceTray, x, y)
res++
}
}
}
return res
}
// (x, y) 위치를 받아 해당 위치에서 인접한 0들을 모두 1로 바꿈(얼려버림)
function freezeSoda(N, M, iceTray, x, y) {
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
const queue = []
// 2차원 배열로 선언!
const visited = Array.from(Array(M), () => new Array(N).fill(false))
// 처음 시작 지점 큐에 저장
queue.push([x, y])
let current // 그래프에서 현재 위치
while (queue.length) {
current = queue.shift()
const [curX, curY] = current
// 현재 위치를 0에서 1로 바꿔 얼려버림
iceTray[curY][curX] = 1
// 최근 위치를 간 곳으로 표시
visited[curY][curX] = true
// 현재 위치에서 보이는 위/아래/왼쪽/오른쪽 4방향에 대해서
for (let i = 0; i < 4; i++) {
// 다음 위치 설정
const nextX = curX + dx[i]
const nextY = curY + dy[i]
// 만약 다음 위치가 갈 수 없는 곳이면 무시
if (nextX < 0 || nextX >= M || nextY < 0 || nextY >= N) continue
// 만약 다음 위치가 벽이라면(1이라면) 무시
if (iceTray[nextY][nextX] === 1) continue
// 아직 가지 않은 곳이라면
if (!visited[nextY][nextX]) {
queue.push([nextX, nextY]) // 큐에 저장
}
}
}
return iceTray // 한 구역 얼린 뒤의 얼음판 반환
}
const N = 4 // 세로 길이
const M = 5 // 가로 길이
const iceTray = [ // 얼음 틀
[0, 0, 1, 1, 0],
[0, 0, 0, 1, 1],
[1, 1, 1, 1, 1],
[0, 0, 0, 0, 0]
]
console.log(solution(N, M, iceTray)) // 결과 : 3
BFS는 DFS와는 다른 장점이 하나 더 있다. 바로 최단경로를 구할 수 있다는 점이다. 예를 들어 어떤 미로가 있는데 시작지점부터 끝까지 최단거리를 구하고 싶다면 BFS로 단번에 구할 수가 있다. 최단경로 문제 하나랑 최단경로인 이유는 아래에서 확인할 수 있다.
게임 맵 최단거리(프로그래머스, Lv. 2) : https://programmers.co.kr/learn/courses/30/lessons/1844
BFS가 최단경로인 이유 : https://nulls.co.kr/graph/141