[JS] 프로그래머스 아이템 줍기 (BFS)

 

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

프로그래머스

 

문제 ↑

 

문제 풀이를 위한 핵심 포인트

 

1. 좌표를 전부 2배수 해주기

 

그림을 그려보면 알겠지만 사각형 끼리의 x변이나 y변의 길이 차이가 1일 경우에 문제가 발생한다. 테두리가 파여 있음에도 2차원 배열로 표현하면 이를 구별할 수 없게 된다. 따라서 x2를 통해 인위적으로 변의 길이 차이가 최소 2 이상이 되도록 바꿔준다.

 

2. 사각형의 테두리는 x좌표 시작점 끝점, y좌표 시작점, 끝점만 알면 편하다.

 

가령 [1,1,7,14] 인경우 x가 1이거나 7인 좌표, y가 1이거나 14인 좌표만 체크하면 테두리만 뽑아낼 수 있다.

 

 

그럼 코드 START

(주석 설명 있음)

function solution(rectangle, characterX, characterY, itemX, itemY) {
    const board = Array.from(Array(103).fill(0), () => Array(103).fill(0)); // 이중배열 만들기

    const doubleRectangle = rectangle.map((arr) => {
        return arr.map((v) => v * 2);
    }); // 좌표 2배수 해주기

    characterX = characterX * 2;
    characterY = characterY * 2;
    itemX = itemX * 2;
    itemY = itemY * 2;

    //좌표 2배수

    //board 채우기
    doubleRectangle.forEach((loc) => {
        console.log(loc);
        for (let i = loc[0]; i <= loc[2]; i++) {
            for (let j = loc[1]; j <= loc[3]; j++) {
                if (i == loc[0] || i == loc[2] || j == loc[1] || j == loc[3]) {
                    if (board[i][j] == 0) board[i][j] = 1;
                } else {
                    board[i][j] = 2;
                }
            }
        }
    });

    //방문 check 이중 배열 만들기
    const visited = Array.from(Array(103).fill(false), () => Array(103).fill(false));
    //queue 돌리기

    const start = [characterX, characterY, 0]; //현재 위치와 cnt

    const queue = [start];

    const directionX = [0, 1, 0, -1];
    const directionY = [1, 0, -1, 0];

    while (queue.length) {
        const [curX, curY, cnt] = queue.shift();
        visited[curX][curY] = true; //방문 chk

        if (curX == itemX && curY == itemY) return cnt / 2;

        for (i = 0; i < 4; i++) {
            //좌표 이동하는 반복문
            const [nx, ny] = [curX + directionX[i], curY + directionY[i]];
            if (board[nx][ny] == 1 && !visited[nx][ny]) {
                queue.push([nx, ny, cnt + 1]);
            }
        }
    }
}

console.log(
    solution(
        [
            [1, 1, 7, 4],
            [3, 2, 5, 5],
            [4, 3, 6, 9],
            [2, 6, 8, 8],
        ],
        1,
        3,
        7,
        8
    )
);