프로그램머스 코딩테스트 - 피코쳇 로봇

문제 설명

제한사항

해결방법

최소 경로를 찾아야 하기 때문에 BFS를 사용하면 될 것 같다.

아이디어

• 일단 문자열 배열로 되어 있는 보드를 2차원 배열로 변환
• BFS를 위한 노드의 위치 정보와 이동 횟수를 담은 큐 배열 생성
• 이미 방문한 노드에 대한 정보를 담은 2차원 배열 생성 (이미 방문한 노드는 큐에 넣어도 최소 경로가 될 수 없음)
• 탐색 진행
  • 노드의 위치에서 상하좌우 중 한 방향씩 장애물이나 가장자리까지 이동
    • 멈춘 위치가 골이라면 이동 횟수 + 1반환
    • 멈춘 위치가 방문한 적 없다면
      • 큐에 멈춘 위치 정보와 이동 횟수 + 1 저장
      • 방문 정보 저장
• 큐를 끝까지 돌았음에도 골이 아니라면 -1 반환

결과 코드

function solution(board) {
    const map = board.map(b => b.split(""));
    const moveX = [1, -1, 0, 0], moveY = [0, 0, 1, -1];
    const xLen = board.length, yLen = board[0].length;
    let x = 0, y = 0;
    
    const queue = []
    const visited = map.map((m, mIdx) => m.map((n, nIdx) => {
        if (n === "R") {
            queue.push([mIdx, nIdx, 0])
            return 1;
        }
        return 0
    }))
    
    while(queue.length) {
        const [xNode, yNode, count] = queue.shift();
        
        for(let i = 0; i < 4 ; i++) {
            x = xNode, y = yNode;
            while (x < xLen && x >= 0 && y < yLen && y >= 0 && map[x][y] !== "D") {
                x += moveX[i];
                y += moveY[i];
            }
            x -= moveX[i];
            y -= moveY[i];
            
            if (map[x][y] === "G") {
                return count + 1;
            }
            if (visited[x][y] === 0) {
                queue.push([x, y, count + 1])
                visited[x][y] = 1
            }
        }
    }
    return -1;
}