PGMS - 아이템줍기

https://programmers.co.kr/learn/courses/30/lessons/87694

코딩테스트 연습 - 아이템 줍기

function solution(rectangle, characterX, characterY, itemX, itemY) {
    var answer = 0;
    let arr = Array.from(Array(200), ()=>Array(200).fill(0));
    let visited = Array.from(Array(200), ()=>Array(200).fill(0));
    rectangle.forEach(([x1,y1, x2,y2])=>{
        for(let i = x1*2; i<=x2*2; i++){
            for(let j = y1*2; j<=y2*2; j++){
                arr[j][i] = 1;
            }
        }
    })
    let queue = [];
    let dir = [[0,1],[0,-1],[1,0],[-1,0]];
    queue.push([characterY*2,characterX*2,0]);
    visited[characterY*2][characterX*2] = 1;
    while(queue.length){
        let [y,x,cnt] = queue.shift();
        if(y==itemY*2&&x==itemX*2){
            return cnt/2;
        }
        for(let i = 0 ; i < 4; i++){
            let dy= dir[i][0];
            let dx = dir[i][1];
            let ty = dy+y;
            let tx = dx+x;
            if(!check(ty,tx)&& ty>=0&&tx>=0&&arr[ty][tx]==1&&visited[ty][tx]!=1){
                queue.push([ty,tx,cnt+1]);
                visited[ty][tx]=1;
            }
        }
    }
    return answer;
    function check(a,b){
    return arr[a][b-1]&&arr[a][b+1]&&arr[a-1][b]&&arr[a+1][b]&&arr[a-1][b-1]&&arr[a-1][b+1]&&arr[a+1][b-1]&&arr[a+1][b+1]
}
}

어찌보면 간단하고, 어찌보면 어려운 문제였다.

 

처음 생각했던 것은 이렇다.

 

최단 경로를 구하는 것은 BFS를 사용하면 되는데, 테두리를 어떻게 갈것인가?

 

자기 자신을 제외하고 모든 면에 다 1이면 그건 안쪽이 아닐까 라고 생각했었고, 그렇게 구현을 했더니 예외 케이스가 생겼다.

 

이렇게 각져있는 경우, 제대로 테두리 부분이지만 주변 부분이 모두 1이라 제대로 순회하지 못한다.

 

두번쨰 케이스는 너비가 1인 얇은 사각형인 경우에 테두리가 아닌데 테두리라고 판단해 가로질러가는 경우가 생겼다.

 

 

이런 케이스를 해결하기 위해서 나는 모든 사각형과 시작 포인트와 도착 포인트의 너비를 2배로 늘렸고, 이랬더니 예외 케이스가 해결되면서 문제가 풀렸다.