Programmers_87694 아이템 줍기

function solution(rectangle, characterX, characterY, itemX, itemY) {
    // 다른 사각형의 안에 있는 점인지 확인하는 함수
    function isInside(idx, x, y) {
        for (let i = 0; i < rectangle.length; i += 1) {
            if (i === idx) continue;

            const [minX, minY, maxX, maxY] = rectangle[i];
            if (2 * minX < x && x < 2 * maxX && 2 * minY < y && y < 2 * maxY) {
                return true;
            }
        }
        return false;
    }

    // canVisit 배열 생성
    const [maxX, maxY] = rectangle.reduce(
        (acc, curr) => [Math.max(acc[0], curr[2]), Math.max(acc[1], curr[3])],
        [0, 0]
    );
    const canVisit = Array.from(new Array(2 * (maxY + 1)), () => new Array(2 * (maxX + 1)).fill(0));

    rectangle.forEach(([minX, minY, maxX, maxY], i) => {
        for (let x = 2 * minX; x <= 2 * maxX; x += 1) {
            [2 * minY, 2 * maxY].forEach((y) => {
                if (!isInside(i, x, y)) {
                    canVisit[y][x] = 1;
                }
            });
        }
        for (let y = 2 * minY; y <= 2 * maxY; y += 1) {
            [2 * minX, 2 * maxX].forEach((x) => {
                if (!isInside(i, x, y)) {
                    canVisit[y][x] = 1;
                }
            });
        }
    });

    // BFS (경로 탐색)
    canVisit[characterY * 2][characterX * 2] = 0;

    const queue = [[characterX * 2, characterY * 2, 0]];
    const dx = [1, 0, -1, 0];
    const dy = [0, 1, 0, -1];

    while (queue.length) {
        const [x, y, count] = queue.shift();

        if (x === 2 * itemX && y === 2 * itemY) return count / 2;

        for (let i = 0; i < 4; i += 1) {
            const nx = x + dx[i];
            const ny = y + dy[i];

            if (canVisit[ny]?.[nx]) {
                canVisit[ny][nx] = 0;
                queue.push([nx, ny, count + 1]);
            }
        }
    }
}

function solution(rectangle, characterX, characterY, itemX, itemY) {
    const MAX = 52;
    const isOnRect = Array.from({ length: MAX }, () => Array(MAX).fill(0));
    rectangle.forEach(([minX, minY, maxX, maxY]) => {
        for (let x = minX; x < maxX; x++) {
            for (let y = minY; y < maxY; y++) {
                isOnRect[x][y] = 1;
            }
        }
    });

    // BFS
    const visited = isOnRect.map(() => Array(MAX).fill(false));
    const queue = new Set([[0, characterX, characterY]]);
    for (const nowSet of queue) {
        queue.delete(nowSet);
        const [count, x, y] = nowSet;

        visited[x][y] = true;
        if (x === itemX && y === itemY) return count;

        const delta = [[-1, -1], [0, -1], [-1, 0], [0, 0]];
        const [leftBottom, bottom, left, now] = delta.map(
            ([dx, dy]) => isOnRect[x + dx]?.[y + dy] ?? 0
        );

        // move left
        if (leftBottom !== left && !visited[x - 1][y])
            queue.add([count + 1, x - 1, y]);
        // move bottom
        if (leftBottom !== bottom && !visited[x][y - 1])
            queue.add([count + 1, x, y - 1]);
        // move top
        if (left !== now && !visited[x][y + 1]) queue.add([count + 1, x, y + 1]);
        // move right
        if (bottom !== now && !visited[x + 1][y])
            queue.add([count + 1, x + 1, y]);
    }
}