[프로그래머스] Lv.2 게임 맵 최단거리 (BFS) + 반례 14개, 연습용 좌표판 PDF

게임 맵 최단거리

 

 

시작 지점부터 도착 지점까지 최단거리로 방문했을 때, 얼마나 걸리는지를 물어보는 문제이다.

예제의 경우 11 이다.

 

최단거리가 DFS 가 아닌 BFS 인 이유

한 지점에서 갈 수 있는 위치 (동일 depth) 를 순차적으로 방문해야 한다. 따라서 가능한 경우의 수를 queue 에 쌓아서 동일 depth 에서 처리해줘야 한다.

 

DFS 는 동일 depth 를 순차적으로 방문하는 것이 아니라, depth 를 파고들어간다. (계속해서 함수를 호출한다) 따라서 최단경로가 아님에도, 이미 간 길을 그대로 가버린다. 

풀이

코드 구조

• 한 위치(0, 0)에서 시작한다.
• 다음 위치로 갈 수 있는지 검사한다. (가지치기)
• 갈 수 있는 위치들에 대해서 후보 리스트(candidates) 를 만든다. 이 때 candidates 는 [[x1, y1], [x2, y2], ...] 로 이루어져있다.

 

상하좌우로 어떻게 이동하는가

한 점에서 움직일 수 있는 방향은 우(동), 하(남), 좌(서), 상(북) (시계방향) 으로 네 방향이다.

	우(동)	하(남)	좌(서)	상(북)
x 이동량	0	+1	0	-1
y 이동량	+1	0	-1	0

 

각 x, y 의 이동량을 배열로 만들어두고, 다음 좌표를 계산해야 할 때, 현재 좌표 + 이동량 으로 계산한다.

const xDirection = [0, 1, 0, -1];
const yDirection = [1, 0, -1, 0];

for(let i=0; i<4; i++) {
    const nextX = x + xDirection[i];
    const nextY = y + yDirection[i];

    if(isOk(nextX, nextY, visited)) {
        candidates.push([nextX, nextY]);
        visited[nextX][nextY] = visited[x][y] + 1;
    }
}

 

코드

• 정확성 및 효율성 테스트 모두 통과

const BLOCKED = 0;
let DEST_INDEX_X = -1;
let DEST_INDEX_Y = -1;

const xDirection = [0, 1, 0, -1];
const yDirection = [1, 0, -1, 0];

function solution(maps) {
    DEST_INDEX_X = maps.length - 1;
    DEST_INDEX_Y = maps[0].length - 1;

    // 시작이 가능한지 체크
    if(maps[0][0] === BLOCKED || maps[DEST_INDEX_X][DEST_INDEX_Y] === BLOCKED) return -1;
    // [[1]] 일 때는 무조건 패스
    if(DEST_INDEX_X === 0 && DEST_INDEX_Y === 0 && maps[0][0] === 1) return 1;

    // 도착지점을 들렀는지 체크하기 위해 -1로 둠
    // 만약 -1이 바뀌었다면 들렸다는 것이고, 안바뀌었다면 안들렸다는 의미임
    maps[DEST_INDEX_X][DEST_INDEX_Y] = -1;

    bfs(0, 0, maps);

    // -1 이면 도착지점을 안들렸다는 뜻이니까, -1 반환
    if(maps[DEST_INDEX_X][DEST_INDEX_Y] === -1) return -1
    
    // 도착지점을 들렸다면 maps[DEST_INDEX_X][DEST_INDEX_Y] 반환
    return maps[DEST_INDEX_X][DEST_INDEX_Y];

}

function getRet(maps) {
    return maps[DEST_INDEX_X][DEST_INDEX_Y];
}


// x, y 에서 갈 수 있는 위치를 순차적으로 (함수 호출 없이) 방문해야 하기 때문에 BFS 임
// bfs 함수 내에서는 map 을 visited 로도 사용해서, visited 로 이름 바꿔줌
function bfs(x, y, visited) {
    // 후보들 배열 선언
    let candidates = [];

    // candidates 초기값
    for(let i=0; i<4; i++) {
        const nextX = x + xDirection[i];
        const nextY = y + yDirection[i];

        if(isOk(nextX, nextY, visited)) {
            candidates.push([nextX, nextY]);
            visited[nextX][nextY] = visited[x][y] + 1;

        }
    }

    // 0,0을 방문했으나 BLOCKED 로 한 이유는
    // BLOCKED 를 하지 않으면 다음 step 에서 0,0으로 방문하려 함
    visited[0][0] = BLOCKED;


    // 초기값이 있는 candidates 를 사용해서,
    // 반복해서 다음 후보들을 고른다
    let temp = [];

    while(candidates.length > 0) {
        // 다음 방문 지점
        const [x, y] = candidates.shift();

        for(let i=0; i<4; i++) {
            // 새로운 다음 지점 (nextX, nextY)
            const nextX = x + xDirection[i];
            const nextY = y + yDirection[i];

            // nextX, nextY 로 가도 되는지 체크
            if(isOk(nextX, nextY, visited)) {
                temp.push([nextX, nextY]);
                // 되면, 방문한걸로 함
                visited[nextX][nextY] = visited[x][y] + 1;
            }
        }
        
        // 후보 배열이 비었으면, 다음 지점에 대해서 넣어줌
        // 그리고 초기화
        if(candidates.length === 0) {
            candidates = [...temp];
            temp = [];
        }
    }

    // 후보가 없으면 끝
}

function isOk(x, y, visited) {
    // 0~DEST_INDEX_X 가 아니거나
    if(x < 0 || x > DEST_INDEX_X) return false;
    
    // 0~DEST_INDEX_Y 가 아니거나
    if(y < 0 || y > DEST_INDEX_Y) return false;

    // BLOCKED 이거나
    if(visited[x][y] === BLOCKED) return false;

    // 이미 들렸거나
    if(visited[x][y] > 1) return false;

    // 모두 통과는 가도 된다는 뜻
    return true;
}

 

반례 14개

const maps1 = [
    [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]
];
console.log('1', solution(maps1)); // 11

const maps2 = [
    [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]
];
console.log('2', solution(maps2)); // -1

const maps3 = [
    [0, 0, 0],
    [0, 0, 0]
];
console.log('3', solution(maps3)); // -1

const maps4 = [
    [0, 0, 1]
];
console.log('4', solution(maps4)); // -1


const maps5 = [
    [1, 1],
    [0, 1]
]
console.log('5', solution(maps5)); // 3



const maps6 = [
    [0, 1]
];

console.log('6', solution(maps6)); // -1

const maps7 = [
    [1, 0],
    [0, 1]
]
console.log('7', solution(maps7)); // -1

const maps8 = [
    [1]
]

console.log('8', solution(maps8)); // 1

const maps9 = [
    [0]
]

console.log('9', solution(maps9)); // -1

const maps10 = [
    [1, 1],
    [1, 0]
]
console.log('10', solution(maps10)); // -1

const maps11 = [
    [1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0],
    [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
    [0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1]
]
console.log('11', solution(maps11)); // 15

const maps12 = [[1, 1, 1, 1, 1]];
console.log('12', solution(maps12)); // 5

const maps13 = [
    [1],
    [1],
    [1],
    [1],
    [1]
];
console.log('13', solution(maps13)); // 5


const maps14 = [
    [1, 1, 1, 1, 1],
    [1, 1, 0, 1, 1],
    [1, 1, 1, 1, 0],
    [1, 1, 0, 1, 1],
    [1, 0, 1, 0, 1]
];

console.log('14', solution(maps14)); // 9

 

연습용 좌표판 PDF

아래 세 종류를 각각 두 장씩 만들어놨으니 필요한 부분을 양면인쇄 하시면 됩니다.

 

이 좌표판은 14번째 반례 입니다. 14번째 반례는 DFS 로는 풀 수 없어, 풀면서 많은 도움을 받았던 좌표판이었습니다. 그래서 추가했습니다.

연습용 좌표.pdf

0.16MB