[프로그래머스] 게임 맵 최단 거리 (LV2 - JavaScript)

프로그래머스

1. 문제

제한사항

• maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
  •  n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다. 
• maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다. 
• 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.

입출력 예

maps	answer
[[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
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]]	-1

 

입출력 예 설명

 

2. 오답

function solution(maps) {
    const directions = [
        [0, 1], // 오른쪽
        [1, 0], // 아래쪽
        [0, -1], // 왼쪽
        [-1, 0], // 위쪽
    ];
    
    const func = (x, y, cnt) => {
    	// 상대팀 진영 (n, m) 위치에 도달하면 종료 
        if(x === maps[0].length-1 && y === maps.length-1) return cnt;
        
        // 현재 위치: 0 -> 재방문 불가
        maps[y][x] = 0;
        // 최단 거리를 담는 변수, Infinity로 초기화
        let optimum = Infinity;
        
        // 4 방향으로 순회
        for (const [dx, dy] of directions) {
            const nx = x + dx;
            const ny = y + dy;

            const canMove = nx >= 0 && ny >= 0 && nx < maps[0].length && ny < maps.length && maps[ny][nx] > 0;
            if (canMove) {
            	이동 가능한 경우 재귀 호출
                const res = func(nx, ny, cnt+1);
                if (res !== -1) {
                	// 4 방향 탐색 후 최단 거리로 optimum 재할당
                    optimum = Math.min(optimum, res);
                }
            }
        }
        maps[y][x] = 1;
        return optimum === Infinity ? -1 : optimum;
    }
    
    return func(0, 0, 1);
}

실행 결과 효율성 테스트에서 처참하게 실패...😥😥

3. 정답 풀이

풀이 전략

• 너비 우선 탐색(BFS, Breadth-First Search) 이용

function solution(maps) {
    const directions = [
        [0, 1], // 오른쪽
        [1, 0], // 아래쪽
        [0, -1], // 왼쪽
        [-1, 0], // 위쪽
    ];
    
    // 이동 가능한지 확인하기 위한 함수
    const canMove = (x, y) => x >= 0 && y >= 0 && x < maps[0].length && y < maps.length && maps[y][x] === 1;
	
    
    const queue = [[0, 0, 1]]; // [x 좌표, y 좌표, 거리] 
    maps[0][0] = 0; // 시작점 재방문 불가 처리
	
    while (queue.length > 0) {
    	// 현재 탐색 위치를 꺼냄
        const [x, y, distance] = queue.shift(); 

        // 상대팀 진영에 도달한 경우 최단거리 반환 후 종료
        if (x === maps[0].length - 1 && y === maps.length - 1) {
            return distance;
        }
        // 4 방향으로 탐색
        for (const [dx, dy] of directions) {
            const nx = x + dx;
            const ny = y + dy;
            // 이동 가능한 경우
            if (canMove(nx, ny)) {
                queue.push([nx, ny, distance + 1]); // 이동 위치를 큐에 추가
                maps[ny][nx] = 0; // 이동 위치 재방문 불가 처리
            }
        }
    }

    return -1;
}

 

 

 

DFS/BFS 등 탐색 알고리즘에 많이 취약한 것 같다...😥😥

문제 풀이도 좋지만 탐색 알고리즘 관련해서 찾아보고 시간 복잡도 고려하면서 풀이도 해봐야겠다.