프로그래머스 [Lv. 3] 아이템 줍기 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(rectangle, characterX, characterY, itemX, itemY) {
    let board = Array(102).fill().map(() => Array(102).fill().map(() => -1));
    const makeRoad = (r, c, q, l) => {
        for (let i = r * 2; i <= q * 2; i++) {
            for (let j = c * 2; j <= l * 2; j++) {
                board[i][j] = 0
            }
        }
    }
    rectangle.forEach(([r, c, q, l]) => makeRoad(r, c, q, l))
    
    const inLine = (r, c) => {
        for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [-1, 1], [1, 1], [1, -1]]) {
            const nr = r + dr;
            const nc = c + dc;
            if ((0 <= nr && nr < 102 && 0 <= nc && nc < 102) && board[nr][nc] == -1) {
                return true
            }
        }
        return false
    }
    
    
    const bfs = () => {
        const q = [[characterX * 2, characterY * 2]];
        board[characterX * 2][characterY * 2] = 1;
        while (q.length) {
            const [x, y] = q.shift();
            if (x == itemX * 2 && y == itemY * 2) {
                return
            }
            for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
                const nr = x + dr;
                const nc = y + dc;
                if ((0 <= nr && nr < 102 && 0 <= nc && nc < 102) && board[nr][nc] == 0 && inLine(nr, nc)) {
                    board[nr][nc] = board[x][y] + 1;
                    q.push([nr, nc])
                }
            }
        }
    }
    bfs()
    const answer = (board[itemX*2][itemY*2] - 1) / 2;
    return answer;
}

풀이 방법

1. 행과 열이 102인 보드를 만든다.
   1. 모두 2배를 해줬기 때문에 50 * 2인데 여분으로 2 더해줬다.
2. 보드에 직사각형의 크기의 2배 만큼 0으로 표시한다.
   1. makeBoard함수로 표시
3. 넓이 우선 탐색을 하는데 시작점과 끝점 또한 2배를 해준다.
4. 0인 지점을 따라가는데 8 방향 중 -1이 있다면 경계선을 잘 따라가고 있는 것이다.
   1. -1이 8방향중 있는지 확인하는 함수 : inLine
   2. 만든 이유는 경계선을 잘 따라가게 하기 위해서
5. 종료지점에 도착하면 바로 return 한다.
6. 종료지점에 거리가 누적된 것을 확인한다.
   1. 계산을 편하게 하기 위해 1을 넣고 시작했기 때문에 -1을 한 뒤 2로 나눈다.

느낀점

• 곱하기 2를 해주는 센스가 돋보였던 문제
  
  • 곱하기 2를 해주는 이유
    • 높이가 1밖에 안되는 직사각형이 있는 경우 경로 탐색시 경계선을 전부 돌지 않고 짧은 경로로 도는 문제가 생겼다.
    • 따라서 2배를 해주면 붙어 있던 부분이 떨어지면서 계산이 편해진다.