https://www.codewars.com/kata/549ee8b47111a81214000941
배운 점
- BFS 너비 우선 탐색 알고리즘
더 연구해볼 점
- DFS 깊이 우선 탐색 알고리즘
Given two different positions on a chess board, find the least number of moves it would take a knight to get from one to the other. The positions will be passed as two arguments in algebraic notation. For example, knight("a3", "b5") should return 1.
The knight is not allowed to move off the board. The board is 8x8.
For information on knight moves, see https://en.wikipedia.org/wiki/Knight_%28chess%29
For information on algebraic notation, see https://en.wikipedia.org/wiki/Algebraic_notation_%28chess%29
(Warning: many of the tests were generated randomly. If any do not work, the test cases will return the input, output, and expected output; please post them.)
이 문제는 이전부터 계속 흥미를 가지고 풀어봐야겠다고 생각한 것이었다.
어릴적 플레이했던 울티마나 넷핵같은 턴제 게임에서 몬스터는 어떻게 플레이어의 위치로 이동하는가?에 대한 궁금증이 있었기 때문이었다.
결과적으로 말하면 BFS 알고리즘에 대한 이해가 없었기 때문에, 계속 고민하다가
https://www.youtube.com/watch?v=js5DMimne-s&t=194s&ab_channel=LeoCrossman
유튜브의 설명을 듣고, 해결해버렸다...
하루 동안 고민한 부분의 코드는 좀 그렇고, 생각했던 점을 몇가지 생각해 보면
- 체스보드의 크기는 8x8이며 확장되지 않는다.
- 따라서, 세로칸은 1부터 8까지, 가로칸은 a부터 h까지 존재한다. 이 알파벳은 그대로 숫자형으로 만드는것이 좋겠다.
- 기사는 한 턴에 총 8가지의 움직임을 가질 수 있다. 체스보드를 벗어나는 움직임은 버린다.
따라서, 내가 생각한 코드는 우선
a. 알아보기 쉽도록 'a1'의 주소 스트링을 [1,1]과 같도록 변환한다.
b. 기사의 8가지 움직임을 코드로 정의한다. 움직인 좌표가 체스보드를 벗어났다면 버린다.
c. 목표점과의 거리를 계산할 수 있도록 해서, 기사의 위치와 목표의 위치를 계속해서 줄여나간다.
내가 풀지 못한 것은 c단계에서의 문제인데, 예를 들면
a1에 기사가, c1에 목표가 있을 경우
기사는 a1, b3, c1으로 총 두 번을 움직여서 도달할 수가 있다.
내가 생각하지 못한 것은 '기사의 중간 지점에서 어디가 최소 경로인지 어떻게 알 수 있는가?' 였다. 1차원적으로 생각했을 때, a1과 c1의 거리보다 b3과 c1의 거리가 더 길기 때문이었다...
상술한 유튜브 해결책에서는 BFS 알고리즘이라는 해결책을 제시하였는데,
이것은 내가 생각한 c와는 접근방법이 아예 달랐다.
즉 '어떤 움직임을 해야 기사가 목표지점에 가장 빠르게 도달할 수 있을까?'
가 아닌
'기사의 모든 움직임을 기록하다보면 언젠가는 도착하지 않을까?'였던 것이다.
위의 관계도를 보면, 시작 지점에서 갈 수 있는 노드들이 존재하고 이를 순차적으로 계산한다. 기사의 움직임을 계산할 수 있도록, Queue 자료구조를 사용한다.
const knight = (start, end) => {
// Gets all knight moves, regardless of validity
const getMoves = loc => {
const moves = [];
moves.push([loc[0] + 1, loc[1] - 2]); // e4 -> c5 왼쪽 두칸, 위 한칸
moves.push([loc[0] + 1, loc[1] + 2]); // e4 -> g5 오른쪽 두칸, 위 한칸
moves.push([loc[0] - 1, loc[1] - 2]); // e4 -> e3 -> c2 왼쪽 두칸, 아래 한칸
moves.push([loc[0] - 1, loc[1] + 2]); // e4 -> e3 -> g3 오른 두칸, 아래 한칸
moves.push([loc[0] + 2, loc[1] - 1]); // e4 -> e6 -> d6 왼쪽 한칸, 위 두칸
moves.push([loc[0] + 2, loc[1] + 1]); // e4 -> e6 -> f6 오른 한칸, 위 두칸
moves.push([loc[0] - 2, loc[1] - 1]); // e4 -> e2 -> d2 왼쪽 한칸, 아래 두칸
moves.push([loc[0] - 2, loc[1] + 1]); // e4 -> e2 -> f2 오른 한칸, 아래 두칸
return moves;
};
// Filters the next move to only be valid on-board moves
const checkMoves = moves => {
return moves.filter(move => {
return move[0] >= 1 && move[0] <=8 && move[1] >= 1 && move[1] <=8
});
};
// Convert square from chess notation to array
const convertPoint = loc => {
const col = {
a: 1,
b: 2,
c: 3,
d: 4,
e: 5,
f: 6,
g: 7,
h: 8,
}
// 'd3' --> [3,4]
const letter = loc.charAt(0);
const num = loc.charAt(1);
return [Number(num), col[letter]];
}
start = convertPoint(start);
end = convertPoint(end);
const board = {};
board[JSON.stringify(start)] = 0;
const q = [start];
while (!(q[0][0] === end[0] && q[0][1] === end[1])) {
const loc = q.shift();
const moves = checkMoves(getMoves(loc));
moves.forEach(move => {
// Add the next move onto the end of the queue
q.push(move);
// Add the new square to the board position and add 1 to it's move count
board[JSON.stringify(move)] = board[JSON.stringify(loc)] + 1;
});
}
return board[JSON.stringify(end)]
}위의 개념을 활용한 해결책은 다음과 같았다.
내가 썼던 코드와 다른 점은
1. Queue를 사용해서 모든 움직임을 저장한다.
2. board 오브젝트를 선언해서, 움직였던 모든 좌표와 움직임의 횟수를 저장한다.
위 생각한 개념은 거의 들어맞았는데, Queue를 활용하여 방문한 모든 장소를 기록하는 것을 생각하지 못했다.
위 BFS 알고리즘도 코드스테이츠에서 분명히 배운 개념인데, 위 문제에서 생각하지 못했다는 것이 아쉽다. 체스를 체스 그 자체로 생각한 것이 문제인 것 같다...
