[프로그래머스] 아이템 줍기

😀풀이과정

1. 좌표 크기를 두배로 해야한다.
   
   테두리를 표현하는 문제 특성상, 붉은 색의 라인으로 가야하지만, 최단거리를 검색하면 푸른 색라인으로 가게되기 때문이며 두배로 풀이한다면 다음과 같이 풀이된다.
   
2. 중복되는 사각형은 다음과 같은 방식으로 제거한다.
   2-1. 모든 좌표의 사각형을 내부까지 채워 그리기
   2-2. 모든 좌표의 사각형의 테두리는 남기고 내부만 지우기

    // 내부까지 모두 채운 사각형 생성
     rectangle.forEach(([sx, sy, ex, ey]) => {
         for(let i = sx*2; i <= ex*2; i++) {
             for(let j = sy*2; j <= ey*2; j++) {
                 board[j][i] = 1;
             }
         }
     });
     // 각 사각형 테두리만 남기고 안쪽 모두 제거
     rectangle.forEach(([sx, sy, ex, ey]) => {
         for(let i = sx*2 + 1; i < ex*2; i++) {
             for(let j = sy*2 + 1; j < ey*2; j++) {
                 board[j][i] = 0;
             }
         }
     });

😎나의 풀이

function solution(rectangle, characterX, characterY, itemX, itemY) {
    // 최대 크기는 50이나, 테두리 표현상의 문제로 2배 크게 작업
    const board = Array.from({length: 101}, () => Array(101).fill(0));
    // 상 하 좌 우 이동
    const directX = [0, 1, 0, -1];
    const directY = [-1, 0, 1, 0];
    
    // 내부까지 모두 채운 사각형 생성
    rectangle.forEach(([sx, sy, ex, ey]) => {
        for(let i = sx*2; i <= ex*2; i++) {
            for(let j = sy*2; j <= ey*2; j++) {
                board[j][i] = 1;
            }
        }
    });
    // 각 사각형 테두리만 남기고 안쪽 모두 제거
    rectangle.forEach(([sx, sy, ex, ey]) => {
        for(let i = sx*2 + 1; i < ex*2; i++) {
            for(let j = sy*2 + 1; j < ey*2; j++) {
                board[j][i] = 0;
            }
        }
    });
    
    // BFS
    const queue = [{x: characterX*2, y: characterY*2, dist: 0}];
    const visited = Array.from({length:101}, () => Array(101).fill(false));
    visited[characterY*2][characterX*2] = true;
    
    while(queue.length > 0) {
        const {x, y, dist} = queue.shift();
        // 2배 크게 했으므로, 1/2 를 반환
        if(x === itemX*2 && y === itemY*2) return Math.floor(dist/2);
        
        for(let i = 0; i < 4; i++) {
            const nextX = x + directX[i];
            const nextY = y + directY[i];
            
            if(nextX < 0 || nextY < 0 || nextX > 100 || nextY > 100) continue;
            if(board[nextY][nextX] === 0 || visited[nextY][nextX]) continue;
            
            visited[nextY][nextX] = true;
            queue.push({x: nextX, y: nextY, dist: dist + 1});
        }
    }
}