[JS] 프로그래머스 게임 맵 최단거리

 

Problem

 

코딩테스트 연습 - 게임 맵 최단거리

---

Solution

 

해당 문제는 BFS로 풀어야 하는 문제입니다.

 

1. 초기 행과 열의 갯수를 저장한다.

 

    const N = maps.length
    const M = maps[0].length

 

2. 상하좌우로 움직일 x와 y의 값을 저장한다.

 

    const direction = [[0, -1], [0, 1], [-1, 0], [1, 0]]

 

3. 맵의 가장자리를 한 겹 감싸준다.

 

맵의 범위를 벗어나게 되면 0으로 간주할 수 있게 가장 자리를 감싸줍니다.

 

    let map = maps
    wrapEdges(map)

 

열의 0번째와 맨 끝번째, 행의 0번째와 맨 끝번째에 0을 넣어줍니다.

 

function wrapEdges(maps) {
    for (m of maps) {
        m.splice(0, 0, 0);
        m.push(0)
    }
    maps.splice(0, 0, new Array(maps.length + 2).fill(0));
    maps.push(new Array(maps.length + 1).fill(0));
}

 

4. BFS로 각 방향으로 움직일 수 있게 진행한다.

 

queue를 만들고 시작점의 위치와 움직인 횟수를 넣어줍니다.

 

map에 시작 지점을 0으로 만들어 줍니다.

 

  let queue = [[1, 1, 1]]
  map[1][1] = 0

 

queue에서 첫 번째 값을 꺼내어 목표 지점(N,M)에 도착하였다면 움직인 횟수를 반환해 줍니다.

 

그게 아니라면  각 방향마다 캐릭터의 위치를 바꿔 진행해 줍니다.

 

단, 무한 루프를 막기 위해 이미 방문하였다면 해당 위치를 0으로 바꿔줍니다.

 

    while (queue.length > 0) {
        const [x,y,count] = queue.shift()
        if (x == N && y == M) {
            return count
        }

        for (d of direction) {
            const next = [x + d[0],y + d[1],count+1]
            if (map[next[0]][next[1]] === 1) {
            map[next[0]][next[1]] = 0
            queue.push(next)
            }
        }
    }

 

5. 캐릭터가 목표 지점을 오지 못한다면 -1을 반환한다.

 

while문 안에서 return이 발생하지 않았다면 목표 지점을 오지 못한 것이므로 -1을 반환해 줍니다.

 

    return -1

---

Source Code

 

---

P.S

 

오랜만에 JS로 알고리즘을 풀었는데 Swift와 같이 struct를 만들지 못해 map을 이용해 객체처럼 풀었는데 런타임 에러가 발생했다.

 

예를 들면 방향을 정할 때 {x:0,y:1}, 큐 안에 들어갈 정보도 {x:0,y1,count:1} 이런 식으로 풀었는데 다음부터는 그냥 배열로 풀어야겠다..