게임 맵 최단거리
게임 맵 최단거리
상당히 억까가 많은 문제였다.
이 문제는 전형적인 미로탐색 알고리즘이므로 따로 설명을 하지는 않겠다.
정확성 테스트는 꽤 빨리 통과했지만 효율성 테스트가 어찌나 빡빡하게 설정돼있는지 내가 모르는 영역의 최적화까지 땡겨와서(그렇다. 이번 문제는 질문 게시판을 참고했다) 겨우 문제가 풀렸다.
참고로 아래 모든 풀이는 모두 최단 거리를 찾는다. 즉 모두 정확성 테스트를 통과한다.
풀이
DFS
let shortest = Infinity;
function pf(maps, pos, goal, n = 0, visited = []) {
const [x, y] = pos;
visited.push([x, y]);
if (n >= shortest) return;
maps[y][x] = 0;
if (x === goal[0] && y === goal[1]) {
shortest = n;
return;
}
const possible = [
[x, y + 1],
[x + 1, y],
[x, y - 1],
[x - 1, y],
];
let next = [];
for (let fw of possible) {
const [x, y] = fw;
if (maps[y][x] === 0) continue;
pf(maps, [x, y], goal, n + 1, visited);
const [px, py] = visited.pop();
maps[py][px] = 1;
}
return shortest;
}
function solution(maps) {
const w = maps[0].length;
const h = maps.length;
// Add border
maps = [
[...Array(w + 2).fill(0)],
...maps.map((n) => [0, ...n, 0]),
[...Array(w + 2).fill(0)],
];
pf(maps, [1, 1], [w, h]);
return shortest === Infinity ? -1 : shortest + 1;
}
첫 번째 정확성 통과 버전이다. 만들기 간편한 DFS알고리즘으로 풀어서, 풀렸다. 아 물론 더 간단한 좌수법이라는 것도 있지만 지도에 대놓고 사이클이 있는데 이 방법으로 풀릴 리는 없다고 생각한다.
A*
위의 DFS 알고리즘에서 아래 부분이 변경되었다.
let next = [];
for (let fw of possible) {
const [x, y] = fw;
if (maps[y][x] === 0) continue;
// Manhattan distance
next.push([goal[0] - x + goal[1] - y, fw]);
}
// A* algorithm
next = next.sort((a, b) => a[0] - b[0]).map((n) => n[1]);
for (let [x, y] of next) {
pf(maps, [x, y], goal, n + 1, visited);
const [px, py] = visited.pop();
maps[py][px] = 1;
}
return shortest;
진짜 A*알고리즘이 이런지는 확신할 수 없다. 내가 아는 바로 A* 알고리즘은 DFS기반이면서 목적지까지의 직선 거리가 더 가까운 노드를 우선 방문한다.
그래서 DFS에서 바뀐 점은 노드 방문 우선순위를 결정하는 로직을 추가한 것이다.
맨하탄 거리는 유클리디안 거리에 비해 오차가 있지만, 어차피 직각으로만 움직이는 이런 미로에서는 맨하탄 거리로도 어떤 노드가 더 가까운지 판단하는데 충분하다. 만약 탐색자가 대각선 방향(즉 8방향)으로도 움직일 수 있다면 맨하탄 거리는 √2 만큼(약 1.4)의 오차가 생겨서 쓸 수 없다.
그리고 Math.abs가 없는 이유는 goal이 이미 지도의 우하단 끝에 있기 때문에 탐색자가 goal의 오른쪽이나 아래쪽을 방문할 가능성이 아예 없기 때문이다.
아 참고로 유클리디안 거리를 구할 때에도 최적화 팁이 있는데, Math.sqrt(Math.pow(x2 - x1, 2)+Math.pow(y2 - y1, 2)) 에서 Math.sqrt는 안 해도 된다. 우리가 원하는 건 상대적으로 더 가까운 거리를 구하는 것이지 거리 자체를 구하려는 게 아니기 때문이다. 제곱하면 음수가 사라지니까 x2-x1이 음수가 되는 걸 걱정할 필요도 없다.
그리고 3차원 이상의 유클리디안 거리를 구하는 방법은 Math.sqrt(Math.pow(x2 - x1, 2)+Math.pow(y2 - y1, 2)+Math.pow(z2 - z1, 2)) 이다. 차원이 늘어날 때마다 그냥 뒤에 붙이면 된다 아무튼 그렇다.
BFS
function pf(maps, pos, goal) {
const [xx, yy] = goal;
let q = [pos];
const visited = new Set();
const path = [];
while (q.length > 0) {
const [x, y] = q.shift();
visited.add(`${x},${y}`);
path.push([x, y]);
// Goal reached
if (x === xx && y === yy) {
let n = 1;
while (path.length > 1) {
const [x, y] = path.pop();
let xx, yy;
do {
[xx, yy] = path.pop();
} while (Math.abs(x - xx) + Math.abs(y - yy) !== 1);
n++;
path.push([xx, yy]);
}
return n;
}
const next = [
[x, y + 1],
[x + 1, y],
[x, y - 1],
[x - 1, y],
];
for (let fw of next) {
const [x, y] = fw;
if (maps[y][x] === 0) continue;
if (visited.has(`${x},${y}`)) continue;
q.push(fw);
}
}
return -1;
}
function solution(maps) {
const w = maps[0].length;
const h = maps.length;
// Add border
maps = [
[...Array(w + 2).fill(0)],
...maps.map((n) => [0, ...n, 0]),
[...Array(w + 2).fill(0)],
];
return pf(maps, [1, 1], [w, h]);
}
안 풀려서 질문 게시판을 방문하니 다들 BFS를 쓰라고 하길래 BFS로 알고리즘을 변경했다.
그리고 제발 질문 게시판에 정답을 올려두진 말아줬으면 한다. 안 보려고 엄청 노력했다.
BFS 알고리즘의 얼개는 ChatGPT가 만들어줬다. 다만 이번엔 저번과 달리 내가 꽤 손을 봤다. ChatGPT가 준 버전은 일반적인 그래프 탐색 알고리즘으로서의 BFS여서 미로탐색 버전으로 좀 최적화를 했다.
알고리즘에서 visited를 삭제하는 로직이 아예 없어서 물어보니, ChatGPT가 답변하길 “BFS는 최초로 발견한 경로가 최단 경로니까 안심하고 쓰셈 ㅇㅇ” 하는 것이었다.
// Goal reached
if (x === xx && y === yy) {
let n = 1;
while (path.length > 1) {
const [x, y] = path.pop();
let xx, yy;
do {
[xx, yy] = path.pop();
} while (Math.abs(x - xx) + Math.abs(y - yy) !== 1);
n++;
path.push([xx, yy]);
}
return n;
}
이 부분을 간단히 설명하자면, 경로를 발견한 경우 목적지로부터 출발지로 역으로 탐색해 나가면서 최단 경로를 그리는 과정이다.
내 이전 노드가 내 이웃 노드가 아닌 경우 노드를 삭제하는 로직인데 내 이전 노드가 이웃 노드가 아닌 건 탐색하다 죽은 탐색자의 흔적이기 때문이다.
하지만 이것도 효율성 테스트를 통과 못했다. 아래는 고통스런 최적화 과정의 결과물이다.
BFS - ver 2
function pf(maps, pos, goal) {
const w = maps[0].length;
const h = maps.length;
const [xx, yy] = goal;
let q = [pos];
const visited = new Set();
const path = [];
while (q.length > 0) {
const pos = q.shift();
path.push(pos);
const [x, y] = pos;
if (x === xx && y === yy) {
let n = 1;
let xx, yy;
for (let i = path.length - 1; i >= 1; ) {
const [x, y] = path[i];
do {
i--;
[xx, yy] = path[i];
} while (Math.abs(x - xx) + Math.abs(y - yy) !== 1);
n++;
}
return n;
}
const next = [
[x, y + 1],
[x + 1, y],
[x, y - 1],
[x - 1, y],
];
for (let fw of next) {
const [x, y] = fw;
if (x < 0 || y < 0 || x >= w || y >= h) continue;
if (maps[y][x] === 0) continue;
if (visited.has(y * w + x)) continue;
visited.add(y * w + x);
q.push(fw);
}
}
return -1;
}
function solution(maps) {
const w = maps[0].length;
const h = maps.length;
return pf(maps, [0, 0], [w - 1, h - 1]);
}
아래 최적화가 적용되었다.
-
map에 border를 넣지 않는다.
대신 map border 판별 로직을 삽입했다.
if (x < 0 || y < 0 || x >= w || y >= h) continue; - path 재구성 로직이 배열 조작을 안 하도록 변경했다.
-
visited set에 노드를 넣을 때
${x},${y}라는 문자열 형태에서 맵 격자의 Unique id로 변경했다.Unique ID는 맵 격자의 일련번호이다. 좌측 상단부터 순서대로 번호를 붙인 것이다. 예를 들어 5x5 미로라면
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 이렇게 일련번호를 붙인 것이다.
-
visited.add()를 현재 방문 노드에 대해서가 아니라 앞으로 방문할 노드에 대해서로 변경했다.이 사소한 변경 하나가 효율성 테스트를 통과시켰다. 솔직히 이건 너무 빡빡하다고 생각한다. BFS 탐색 깊이가 딱 1 늘어나는 것조차 허용하지 않을 정도로 빡빡하다니! 이건 솔직히 억까다. 이건 힌트 못봤으면 훨씬 먼 길을 돌아갔을 뻔했다.
하지만 이 부분은 잘 이해가 안 된다. 방문 기록을 남기는 장소가 현재 탐색자의 위치가 아니라 탐색자가 앞으로 갈 예정인 곳 전부로 변경해도 문제가 풀리다니? 일일이
q를 콘솔 로그로 찍어보면서 이전 버전에서는 중복되는 방문 예정지가 생기는 걸 눈으로 확인하긴 했지만 코드만 봐서는 여전히 이해가 잘 안 된다.
어쨌든, 그래, 풀.렸.다. 하지만 개인적으로 효율성 테스트에 어느 정도 여유가 있어야 한다는 생각이다. 이건 너무 빡빡하지 않은가!
내용추가(2023-05-03) - 최적화 버전
I Asked GPT-4 To Refactor My Legacy Codebase 이거 보고 ChatGPT한테 내 최종 코드를 최적화해보라고 했다. 무료 버전이라서 코드를 생성하다 말았는데 잘린 부분은 내가 알아서 채웠다.
There are a few things that can be optimized in this code to make it faster:
1. Use a queue with a fast shift operation: The current implementation uses an array for the queue and shifts the first element out of the array using shift() on every iteration. This is inefficient since shift() is a relatively slow operation for large arrays. Instead, we can use a double-ended queue (deque) with a fast shift() operation.
2. Avoid creating new arrays: The current implementation creates new arrays for next and fw on every iteration of the loop. This is inefficient since allocating and deallocating memory can take time. Instead, we can reuse the same arrays on every iteration by initializing them once before the loop.
3. Use bitwise operators instead of arithmetic operators: The current implementation uses arithmetic operators (* and /) to calculate the indices of cells in the visited set. This is inefficient since arithmetic operations are generally slower than bitwise operations. Instead, we can use bitwise operators (<< and |) to calculate the indices.
Here's the optimized code with comments explaining the changes:
아 원래 답변 중에 JavaScript has a built-in ArrayDeque class that we can use for this purpose. 도 있었는데 이건 헛소리다. MDN에서 안나오고 caniuse.com 에서도 안나온다.
// Use ArrayDeque for the queue with a fast shift operation
class ArrayDeque {
constructor() {
this._head = [];
this._tail = [];
}
push(value) {
this._tail.push(value);
}
shift() {
if (this._head.length === 0) {
this._head = this._tail.reverse();
this._tail = [];
}
return this._head.pop();
}
isEmpty() {
return this._head.length === 0 && this._tail.length === 0;
}
values() {
return this._head.concat(this._tail);
}
}
function pf(maps, pos, goal) {
const w = maps[0].length;
const h = maps.length;
const [xx, yy] = goal;
// Initialize deque, visited set, and path array
const q = new ArrayDeque();
const visited = new Set();
visited.add((pos[1] << 16) | pos[0]);
q.push(pos);
const path = [];
const next = [
[0, 1],
[1, 0],
[0, -1],
[-1, 0],
];
const fw = [0, 0];
while (!q.isEmpty()) {
const pos = q.shift();
path.push(pos);
const [x, y] = pos;
if (x === xx && y === yy) {
let n = 1;
let xx, yy;
for (let i = path.length - 1; i >= 1; ) {
const [x, y] = path[i];
do {
i--;
[xx, yy] = path[i];
} while (Math.abs(x - xx) + Math.abs(y - yy) !== 1);
n++;
}
return n;
}
// Iterate over next array and reuse fw array on every iteration
for (let i = 0; i < 4; i++) {
fw[0] = x + next[i][0];
fw[1] = y + next[i][1];
if (fw[0] < 0 || fw[1] < 0 || fw[0] >= w || fw[1] >= h) continue;
if (maps[fw[1]][fw[0]] === 0) continue;
const index = (fw[1] << 16) | fw[0];
if (visited.has(index)) continue;
visited.add(index);
q.push([...fw]);
}
}
return -1;
}
function solution(maps) {
const w = maps[0].length;
const h = maps.length;
return pf(maps, [0, 0], [w - 1, h - 1]);
}
이 코드의 효율성 테스트 결과는 아래와 같다.
효율성 테스트
테스트 1 〉 통과 (43.55ms, 39.1MB)
테스트 2 〉 통과 (5.28ms, 34.3MB)
테스트 3 〉 통과 (39.14ms, 38.4MB)
테스트 4 〉 통과 (7.93ms, 35.1MB)
기존 코드의 효율성 테스트 결과는 아래와 같다.
효율성 테스트
테스트 1 〉 통과 (45.34ms, 42MB)
테스트 2 〉 통과 (6.53ms, 35.2MB)
테스트 3 〉 통과 (28.79ms, 40.5MB)
테스트 4 〉 통과 (23.84ms, 39.4MB)
어… ChatGPT가 거짓말했나? 하여튼간에 이런 테크닉도 있다 정도 배워간다. ArrayDeque는 유용하게 써먹을 수 있을 것 같다.
댓글남기기