문제
ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.
지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.
위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.
첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.
두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.
위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.
만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.
게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.
제한 사항
maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.
입력
maps : [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]]
출력
11
내가 했던 풀이 방법
- maps 배열의 length를 이용하여 width와 height를 저장한 뒤, maps와 같은 크기의 2차원 배열을 만들고 false로 채워준다.
- queue 배열을 만들고, [0, 0, 1]을 추가해준다. (해당 배열은 x좌표, y좌표, 현재까지 distance를 의미한다.
- queue가 빈 배열이 되거나 x, y가 목적지인 (n, m)에 도달하게 될 때까지 반복한다. queue에서 맨 앞에 있는 요소를 가져와 x, y, dist에 저장해준다. 이때, 빈 배열이 되어 끝나는 경우는 목적지에 도달하지 못한다는 뜻이므로 그대로 반복문을 끝내주고, 목적지에 도달하면 현재까지의 distance를 반환해준다.
- 상하좌우 방향 중 index 범위를 벗어나지 않으면서, 이동할 수 있는 공간이 있는 경우(maps[y][x]===1)이면서 아직 방문하지 않은 위치인 경우(visted[y][x]===false) 해당 위치와 distance+1을 포함한 배열을 queue에 추가해준 뒤, visited를 true로 바꾸어준다.
- 반복문이 탈출했음에도 반환되지 않았음은 목적지를 찾지 못한 것이므로 -1을 return 해준다.
코드
function solution(maps) {
let width = maps[0].length;
let height = maps.length;
let visited = Array.from({length: height}, ()=>Array(width).fill(false));
let queue = [];
queue.push([0, 0, 1]);
visited[0][0] = true;
while(true) {
if(queue.length===0) break;
let [x, y, dist] = queue.shift();
if(x===width-1 && y===height-1) {
return dist;
}
if(x-1>=0 && maps[y][x-1]===1 && !visited[y][x-1]) {
queue.push([x-1, y, dist+1]);
visited[y][x-1] = true;
}
if(x+1<width && maps[y][x+1]===1 && !visited[y][x+1]) {
queue.push([x+1, y, dist+1]);
visited[y][x+1] = true;
}
if(y-1>=0 && maps[y-1][x]===1 && !visited[y-1][x]) {
queue.push([x, y-1, dist+1]);
visited[y-1][x] = true;
}
if(y+1<height && maps[y+1][x]===1 && !visited[y+1][x]) {
queue.push([x, y+1, dist+1]);
visited[y+1][x] = true;
}
}
return -1;
}회고
또 DFS로 풀었다가 불가능이라는 것을 깨닫고 BFS로 바꿔서 풀이했다. 최단거리는 BFS로 풀이한다는 것을 최근에 공부하긴 했지만, DFS로도 풀 수 있겠는데?라는 생각이 들어서 구현을 했고, 실제로도 제대로 구현하긴 했지만, 효율성에서 0점을 맞았다. 알고보니 최단거리를 풀 때 DFS는 지~~~인짜 웬만하면 시간초과가 걸린다고 한다. 그래서 BFS로 풀이를 해보았다. 하지만, BFS에서도 효율성 때문에 계속 틀리게 됐는데 처음에 생각한 방식은 이전에 BFS를 배웠던 그대로 predecessor를 추가하여 n, m에서 backtracking을 해주었다. 하지만, 어디 경로를 지나갔는지가 궁금하진 않고, 얼만큼 걸리느냐만 필요했기 때문에 predecessor가 필요없다는 걸 알고 코드를 수정하여 queue에 들어갈 배열에 distance를 추가해주었다. 그럼에도 시간초과는 해결되지 않았는데 queue에 인접한 좌표를 넣어줄 때 visited도 같이 true로 설정해주지 않아서였다. 기존에는 while문 초반에 x, y 좌표를 받아오면 그때서야 visited를 true로 설정해주었는데, 해당 경우 이미 방문했던 좌표를 다시 queue에 넣을 수 있다고 해서 위치를 바꿔주었다. 사실 왜.... 방문했던 좌표가 queue에 들어가게 되는지는 잘 모르겠다. 특정 경우에 그럴 수 있겠거니... 뭐 그럴 수 있겠지... 싶긴한데 지금 코드에서 그럴 일이 있나? 싶긴한데 뭐... 일단 이 부분은 좀 더 알아봐야 할 것 같다.
