문제
건설회사의 설계사인 죠르디는 고객사로부터 자동차 경주로 건설에 필요한 견적을 의뢰받았습니다.
제공된 경주로 설계 도면에 따르면 경주로 부지는 N x N 크기의 정사각형 격자 형태이며 각 격자는 1 x 1 크기입니다.
설계 도면에는 각 격자의 칸은 0 또는 1 로 채워져 있으며, 0은 칸이 비어 있음을 1은 해당 칸이 벽으로 채워져 있음을 나타냅니다.
경주로의 출발점은 (0, 0) 칸(좌측 상단)이며, 도착점은 (N-1, N-1) 칸(우측 하단)입니다. 죠르디는 출발점인 (0, 0) 칸에서 출발한 자동차가 도착점인 (N-1, N-1) 칸까지 무사히 도달할 수 있게 중간에 끊기지 않도록 경주로를 건설해야 합니다.
경주로는 상, 하, 좌, 우로 인접한 두 빈 칸을 연결하여 건설할 수 있으며, 벽이 있는 칸에는 경주로를 건설할 수 없습니다.
이때, 인접한 두 빈 칸을 상하 또는 좌우로 연결한 경주로를 직선 도로 라고 합니다.
또한 두 직선 도로가 서로 직각으로 만나는 지점을 코너 라고 부릅니다.
건설 비용을 계산해 보니 직선 도로 하나를 만들 때는 100원이 소요되며, 코너를 하나 만들 때는 500원이 추가로 듭니다.
죠르디는 견적서 작성을 위해 경주로를 건설하는 데 필요한 최소 비용을 계산해야 합니다.
도면의 상태(0은 비어 있음, 1은 벽)을 나타내는 2차원 배열 board가 매개변수로 주어질 때, 경주로를 건설하는데 필요한 최소 비용을 return 하도록 solution 함수를 완성해주세요.
제한사항
- board는 2차원 정사각 배열로 배열의 크기는 3 이상 25 이하입니다.
- board 배열의 각 원소의 값은 0 또는 1 입니다.
- 도면의 가장 왼쪽 상단 좌표는 (0, 0)이며, 가장 우측 하단 좌표는 (N-1, N-1) 입니다.
- 원소의 값 0은 칸이 비어 있어 도로 연결이 가능함을 1은 칸이 벽으로 채워져 있어 도로 연결이 불가능함을 나타냅니다.
- board는 항상 출발점에서 도착점까지 경주로를 건설할 수 있는 형태로 주어집니다.
- 출발점과 도착점 칸의 원소의 값은 항상 0으로 주어집니다.
입출력 예
| board | result |
|---|---|
| [[0,0,0],[0,0,0],[0,0,0]] | 900 |
| [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] | 3800 |
| [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] | 2100 |
| [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[0,1,0,0,0,1],[0,0,0,0,0,0]] | 3200 |
풀이
문제를 간단하게 요약하면 다음과 같습니다.
- 2차원 배열로 이루어진 board에서 (0, 0)부터 (N-1, N-1)까지 가는 최단 경로를 구하라.
- 원소의 값이 1인 경우는 벽으로 지나갈 수 없다. (원소의 값이 0인 경우만 지나갈 수 있다.)
- 각 이동의 가중치는 직전과 이동 방향이 같을 경우 100, 다를 경우 600이다.
- (0, 0)부터 (N-1, N-1)까지 가는 경로는 항상 존재한다.
그렇다면 이 문제를 풀기 위해서 출발부터 도착까지 최단 경로를 구할 수 있는 방법이 필요합니다. 그리고 가중치를 계산할 방법도 필요합니다. 제가 아는 한 최단 경로를 구하는 알고리즘은 모두 어렵지 않게 가중치를 넣어 줄 수 있습니다. 그렇지만 이 문제는 현재까지 어떤 경로로 통과했느냐에 따라 가중치가 달라집니다. 정확하게는 이전의 위치와 현재 위치, 이동할 위치 3가지 변수를 가지고 가중치를 정하게 됩니다. 가중치가 정해져 있다면 최단 경로를 구하는 것은 어렵지 않으나 가중치를 어떻게 계산할지가 이 문제 풀이의 핵심입니다.
스택 자료 구조와 DFS를 활용한 풀이
먼저 스택 자료 구조와 DFS를 활용한 풀이입니다.
function solution(board) {
const boardSize = board.length - 1;
const visit = board.map((e) => e.map((e) => Infinity));
const stack = [];
stack.push([0, [0, 0], 4]);
const dir = [
[0, 1],
[0, -1],
[1, 0],
[-1, 0],
];
while (stack.length) {
const [cost, curLocation, lastMove] = stack.pop();
if (cost > visit[curLocation[0]][curLocation[1]] + 499) continue;
if (cost < visit[curLocation[0]][curLocation[1]]) {
visit[curLocation[0]][curLocation[1]] = cost;
}
for (let direction = 0; direction < 4; direction++) {
const [ni, nj] = [dir[direction][0] + curLocation[0], dir[direction][1] + curLocation[1]];
if (ni < 0 || ni > boardSize || nj < 0 || nj > boardSize) continue;
if (board[ni][nj] === 1) continue;
let newCost = cost;
if (lastMove === direction || lastMove === 4) {
newCost += 100;
} else {
newCost += 600;
}
stack.push([newCost, [ni, nj], direction]);
}
}
return visit[boardSize][boardSize];
}가중치 계산하기
문제 요약에서 이미 언급했듯이 직전의 이동과 현재의 이동의 방향이 같을 경우는 100, 다를 경우는 600이 됩니다. 커브 도로는 이전의 이동과 방향이 다를 경우에만 존재하기 때문입니다. 그렇다면 이번 이동이 직선 이동인지 아닌지만 파악하면 됩니다. 이를 위해 각 이동마다 어느 방향으로 이동했는지에 대한 정보를 저장하고 다음 이동 방향과 비교하였습니다.
const dir = [[0, 1], [0, -1], [1, 0],[-1, 0]];
// ...
const [cost, curLocation, lastMove] = stack.pop();
// ...
for (let direction = 0; direction < 4; direction++) {
// direction의 값이 다음 탐색을 위한 이동 방향이 됩니다.
// lastMove === 4인 경우는 처음 출발 시 무조건 직선 도로로 시작하기 때문에 둔 초기값입니다.
// direction은 4가 될 수 없습니다.
if (lastMove === direction || lastMove === 4) {
newCost += 100;
} else {
newCost += 600;
}
stack.push([newCost, [ni, nj], direction]);
}
// ...dir 배열은 어느 방향으로 이동할지 정하는 배열입니다. 만약 dir[1]이라면 같은 행의 다음 열로 이동하는 방식입니다. 다들 익숙하실 테니 더 설명하지는 않겠습니다. 문제에서 중요한 것은 어느 방향으로 이동했는지에 대한 정보입니다. dir이 이미 방향을 나타내고 있으니 dir의 몇 번 인덱스가 이번 이동에 사용되었는지 파악하면 어느 방향으로 이동했는지에 대해 알 수 있습니다. 그래서 dir을 순환하는 for문의 변수를 direction으로 지정하였습니다. 그리고 이 변수는 이동 정보로 함께 저장이 됩니다.
최적 경로 계산하기
이 문제의 핵심은 도착지까지 몇 번의 커브 도로가 필요한지입니다. 같은 위치에 도착했을 때 커브의 횟수가 더 적다면 그것이 최소 가중치를 가진 경로(최적 경로)이기 때문입니다. (x, y)까지 도착한 하나의 경로는 마지막 이동이 오른쪽으로 이동한 것에 가중치의 합이 1500이고 다른 경로는 아래로 이동한 것으로 가중치가 1200일때, 만약 다음 최단 경로로 가기 위해 오른족으로 이동해야 한다면 전자의 경로가 최적 경로가 될 것입니다. 그래서 더 적은 가중치로 이미 방문한 지점이라도 가중치를 다시 비교해 볼 필요가 있습니다.
// 방향이 다르다고 해도 500 이상의 차이는 무시해도 됩니다.
if (cost > visit[curLocation[0]][curLocation[1]] + 499) continue;
if (cost < visit[curLocation[0]][curLocation[1]]) {
visit[curLocation[0]][curLocation[1]] = cost;
}
여기서 cost는 현재 위치까지 이동한 경로에 대한 가중치의 합입니다. visit는 각 위치까지 이동가능한 최소 가중치를 저장한 2차원 배열입니다. 그런데 특이한 점이 있습니다. 현재 가중치가 기존의 최소 가중치와 499의 합보다 크다면 해당 경로로는 더 이상 탐색하지 않습니다.
이유는 커브 도로와 직선 도로의 가중치 차이가 500이기 때문인데요. 앞서 언급했듯이 어떤 지점에서 도착한 방향에 따라 다음 이동의 가중치가 차이가 나는데 그 차이가 500이라는 말입니다. 따라서 정확히 500만큼의 차이가 난다면 다음 이동에서 이득을 보지는 못합니다. 예를 들어봅시다. (x, y)에 도착한 두 개의 경로가 있습니다. 하나는 직전의 방향이 왼쪽에 가중치가 1300이고 다른 경로는 아래 이동에 가중치가 1800입니다. 만약 최적경로로 이동하기 위한 다음 이동 방향이 아래라고 하면 (x, y+1)로 이동한 후의 가중치는 모두 1900이 되고 이동 방향은 아래로 동일하기 때문에 이후로는 중복된 경로가 될 것입니다. 그래서 500보다 더 큰 차이가 나면 굳이 더 탐색하지 않는 것입니다. 사실 500을 더하고 >가 아닌 >= 연산자를 사용한 것이 조금이나마 더 나은 코드가 되었을 것이라는 생각이 듭니다.
최소힙 자료 구조와 다익스트라 알고리즘으로 풀기
이 문제를 더 빠른 시간으로 풀 수 있는 방법이 있습니다. 바로 다익스트라 알고리즘을 이용하는 것인데요. 풀이는 다음과 같습니다.
class MinHeap {
#heap = [];
insert(value) {
this.#heap.push(value);
this.#bubleUp();
}
#bubleUp() {
let index = this.#heap.length - 1;
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.#heap[index][0] >= this.#heap[parentIndex][0]) break;
[this.#heap[index], this.#heap[parentIndex]] = [this.#heap[parentIndex], this.#heap[index]];
index = parentIndex;
}
}
heapPop() {
if (this.#heap.length === 0) return null;
if (this.#heap.length === 1) return this.#heap.pop();
const value = this.#heap[0];
this.#heap[0] = this.#heap.pop();
this.#bubleDown();
return value;
}
#bubleDown() {
let index = 0;
const length = this.#heap.length;
while (index < length) {
const leftIndex = Math.floor(index * 2 + 1);
const rightIndex = Math.floor(index * 2 + 2);
let smallestIndex = index;
if (leftIndex < length && this.#heap[leftIndex][0] < this.#heap[smallestIndex][0]) smallestIndex = leftIndex;
if (rightIndex < length && this.#heap[rightIndex][0] < this.#heap[smallestIndex][0]) smallestIndex = rightIndex;
if (smallestIndex === index) break;
[this.#heap[index], this.#heap[smallestIndex]] = [this.#heap[smallestIndex], this.#heap[index]];
index = smallestIndex;
}
}
get size() {
return this.#heap.length;
}
}
function solution(board) {
const boardSize = board.length - 1;
const visit = board.map((e) => e.map((e) => Infinity));
const heapQ = new MinHeap();
heapQ.insert([0, [0, 0], 4]);
const dir = [
[0, 1],
[0, -1],
[1, 0],
[-1, 0],
];
while (heapQ.size) {
const [cost, curLocation, direction] = heapQ.heapPop();
if (cost > visit[curLocation[0]][curLocation[1]] + 499) continue;
if (cost < visit[curLocation[0]][curLocation[1]]) {
visit[curLocation[0]][curLocation[1]] = cost;
}
for (let i = 0; i < 4; i++) {
const [ni, nj] = [dir[i][0] + curLocation[0], dir[i][1] + curLocation[1]];
if (ni < 0 || ni > boardSize || nj < 0 || nj > boardSize) continue;
if (board[ni][nj] === 1) continue;
let newCost = cost;
if (direction === i || direction === 4) {
newCost += 100;
} else {
newCost += 600;
}
heapQ.insert([newCost, [ni, nj], i]);
}
}
return visit[boardSize][boardSize];
}다익스트라 알고리즘은?
다익스트라 알고리즘은 최단 경로를 더욱 빨리 찾기 위해 현재까지 이동 경로 중 가중치가 가장 낮은 경로부터 다음 탐색을 이어갑니다. 그래서 목적지에 도착하는 경로가 생기는 순간 그 경로가 최소 가중치를 가진 경로가 됩니다. 하지만 이 문제는 목적지에 먼저 도착하는 경우가 생겨도 그 다음에 도착하는 경로가 더 적은 커브를 가질 수 있습니다.
(N-2, N-1)로 도착한 두 경로가 있다고 가정합시다. 하나는 가중치 2000, 직전 이동이 오른쪽인 경우이고 다른 하나는 가중치 1900에 직전 이동이 아래쪽인 경우입니다. 그럴 경우 다익스트라는 후자의 탐색을 먼저 진행하여 2500을 최적 경로로 탐색합니다. 전자의 경로가 목적지에 도착하면 2100이 되는 데도 불구하고 말입니다. 결국 다익스트라 알고리즘을 사용하더라도 모든 경로가 목적지에 도착해 봐야 진정한 최적 경로를 찾아낼 수 있습니다. 다익스트라는 이런 경우에도 DFS 혹은 BFS 방식의 탐색보다 훨씬 효율적입니다. visit 배열의 최소값 갱신이 더 효율적으로 발생하기 때문인데요. 그래서 최적 경로가 될 수 없는 경로들을 더욱 빠르게 스킵할 수 있습니다.
다만 다익스트라 알고리즘은 특수한 자료 구조가 필요한데요. 앞서 언급했듯 현재까지의 경로 중 최소 가중치를 가진 경로를 빠르게 찾아내어 꺼낼 수 있어야 합니다. 스택이나 힙 자료 구조는 최소 값을 찾기 위해 모든 요소를 하나씩 확인해야하기 때문에 O(n)의 시간 복잡도가 필요합니다. 만약 다익스트라 알고리즘이 이런 자료구조를 사용했다간 한 번의 탐색마다 O(n)의 시간 복잡도를 가진 계산을 수행해야 합니다.n은 한 번 탐색을 할 때마다 n과 연결된 간선의 수 만큼 늘어나고(여기선 최대 4) 다시 1이 빠지기 때문에 전체 board의 크기가 크면 상당히 비효율 적입니다. 그래서 빠른 시간안에 최소 가중치를 가진 값을 'pop"할 수 있는 자료 구조가 필요합니다. 우선순위 큐 또는 최소힙이 바로 그것입니다.
특수한 자료 구조를 사용한다는 것을 제외하면 BFS나 DFS의 풀이 방법과 큰 차이는 없습니다.
최소힙?
최소 힙(Min Heap)은 이진 트리 기반의 자료 구조입니다.(이진 트리는 설명이 너무 길어져 생략하겠습니다.) 최소 힙의 특징으로는 모든 노드는 자신의 자식 노드들보다 더 작은 값을 가진다는 것이 있습니다. 그래서 루트 노드에는 전체 요소 중 가장 작은 값이 위치하게 됩니다. 반대로 항상 자식 노드들 보다 더 큰 값을 가지는 최대 힙도 존재합니다.
insert(value) {
this.#heap.push(value);
this.#bubleUp();
}
#bubleUp() {
let index = this.#heap.length - 1;
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.#heap[index][0] >= this.#heap[parentIndex][0]) break;
[this.#heap[index], this.#heap[parentIndex]] = [this.#heap[parentIndex], this.#heap[index]];
index = parentIndex;
}
}이진 트리는 값이 들어오고 나갈 때마다 트리를 다시 정렬하는 데요. 트리의 가장 마지막 위치에 값을 넣고, 부모 노드와 비교하여 더 작은 값이면 부모와 자리를 바꾸는 방식입니다. 자신의 부모, 부모의 부모, 부모의 부모의 부모...와만 검사하기 때문에 최대 트리의 높이만큼의 계산 횟수가 필요합니다. 즉 O(log n)의 시간복잡도를 가집니다.
heapPop() {
if (this.#heap.length === 0) return null;
if (this.#heap.length === 1) return this.#heap.pop();
const value = this.#heap[0];
this.#heap[0] = this.#heap.pop();
this.#bubleDown();
return value;
}
#bubleDown() {
let index = 0;
const length = this.#heap.length;
while (index < length) {
const leftIndex = Math.floor(index * 2 + 1);
const rightIndex = Math.floor(index * 2 + 2);
// 왼쪽의 자식과 오른쪽의 자식을 모두 비교하여 더 작은 자식과 자리를 바꿉니다.
let smallestIndex = index;
if (leftIndex < length && this.#heap[leftIndex][0] < this.#heap[smallestIndex][0]) smallestIndex = leftIndex;
if (rightIndex < length && this.#heap[rightIndex][0] < this.#heap[smallestIndex][0]) smallestIndex = rightIndex;
if (smallestIndex === index) break;
[this.#heap[index], this.#heap[smallestIndex]] = [this.#heap[smallestIndex], this.#heap[index]];
index = smallestIndex;
}
}다익스트라 알고리즘에서는 최소 값 pop하는 과정 또한 필요합니다. 최소값은 루트 노드에 존재합니다. 이 값을 조회하는 것은 O(1)의 시간 복잡도가 필요합니다. 다만 루트 노드를 삭제해야 하기 때문에 새로운 최소 값을 루트 노드에 올려야 합니다. 트리를 다시 정렬하는 과정은 다음과 같습니다. 루트에서 값을 삭제하고 트리의 마지막 값을 루트에 넣고 자식들과 비교하면서 더 작은 자식이 있다면 자신과 위치를 바꾸는 것을 반복합니다. 여기서 두 자식 중 더 작은 값을 가진 자식과 위치를 바꿉니다. 그래야 항상 부모의 값이 자식보다 작은 것을 유지할 수 있기 때문입니다.
'알고리즘과 자료구조' 카테고리의 다른 글
| 트라이(Trie): 문자열 탐색과 저장을 효율적으로 만들어주는 자료구조 (0) | 2024.12.08 |
|---|---|
| [BOJ] 백준 1305번 광고 Python (0) | 2023.11.27 |
| [BOJ] 백준 2662번 기업투자 파이썬 Python (0) | 2023.11.16 |