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

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

 

 

문제 설명

다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다.

지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다.

만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다.

단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없습니다.

즉, 위 그림처럼 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없습니다.

다음 그림과 같이 지형이 2개 이상으로 분리된 경우도 없습니다.

한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없습니다.

지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요.

제한사항

• rectangle의 세로(행) 길이는 1 이상 4 이하입니다.
• rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태입니다.
  • 직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다.
  • 서로 다른 두 직사각형의 x축 좌표, 혹은 y축 좌표가 같은 경우는 없습니다.
  • 문제에 주어진 조건에 맞는 직사각형만 입력으로 주어집니다.
• charcterX, charcterY는 1 이상 50 이하인 자연수입니다.
  • 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
• itemX, itemY는 1 이상 50 이하인 자연수입니다.
  • 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
• 캐릭터와 아이템의 처음 위치가 같은 경우는 없습니다.

---

• 전체 배점의 50%는 직사각형이 1개인 경우입니다.
• 전체 배점의 25%는 직사각형이 2개인 경우입니다.
• 전체 배점의 25%는 직사각형이 3개 또는 4개인 경우입니다.

 

 

---

 

 

문제 정리

• 둘레
• 꼭지점에서 만나거나 변이 겹치는 경우 없음, 지형이 분리된 경우도 없음, 완전히 포함 된 것도 없음
• 아이템을 줍기 위해 최소이동거리 구하기

 

생각

시작점에서 target점 까지의 최소 이동거리를 구하니까 bfs를 생각했다.

시작점에서 양 옆으로 2가지 경우를 계속 둘레를 따라 이동하면서 먼저 target에 도달하는 경우의 거리를 리턴하는 것이다.

 

하지만 어떻게 rectangle끼리 겹치는 부분의 둘레를 판단하는지에서 막혔다.

일단 이차배열board상에서 갈 수 있는 곳과 갈 수 없는 곳을 먼저 정리한 뒤 상하좌우를 탐색하며 갈 수 있는 곳을 이동하기로 했다.

 

문제에서 모든 좌표는 50이하인 자연수 => 50*50 board를 만든 뒤 둘레 밖, 둘레, 둘레 안으로 구분하려고 했다.

둘레인지 구분하는 방법

한 rectangle[x1, y1, x2, y2]에서  x가 x1 혹은 x2이거나 y가 y1혹은 y2이면 둘레이다.

 

따라서 모든 rectangle의 x1, y1에서 x2, y2까지 순회하며 둘레 밖/ 둘레/ 안을 각각 0,1,2 로 구분한다.

 

board를 다 정리한 뒤 시작점에서부터 상하좌우가 둘레인지를 확인하며 이동한다.

 

 

먼저 테케3인 경우에 board가 위의 규칙에 따라 잘 변경되는지 확인했다.

 

둘레를 표시한 board 출력

 

아뿔싸 둘레가 배열의 한 칸으로 여겨져서 rectangle의 가로 세로가 1씩 더 길어졌다
둘레를 표시하는 1이 한칸을 차지하기 때문이였다.

 

 

따라서 50*50 board는 크기가 부족하다

만약 50칸 모두 둘레가 생기면 board의 한 변은 기존 50칸 + 둘레 51칸 = 101칸이 필요하다.

넉넉하게 짝수인 102칸으로 board를 만들고 그와 같이

characterX, characterY, itemX, itemY 도 2배를 곱해주었다 

즉 모든 걸 2배로 확장한 거다 (단 나중에 2로 나눠 다시 축소해야하는 걸 잊지말자)

 

• board, characterX, characterY, itemX, itemY 모든 것을 2배로 확장한다
• rectangle을 순회하며 최종 둘레를 board에 정리한다
• 시작점 부터 bfs로 상하좌우를 탐색해 둘레를 따라 이동한다
• target점을 찾으면 리턴한다.

전체 코드

갈 수 있는 곳 정리한 뒤 bfs

function solution(rectangle, characterX, characterY, itemX, itemY) {
    var answer = 0;
    // 2배 확장
    const board = Array.from({length: 102}, () => Array.from({length: 102}, () => 0));
    rectangle = rectangle.map(([a,b,c,d]) => ([a*2, b*2, c*2, d*2]));
    characterX *= 2;
    characterY *= 2;
    itemX *= 2;
    itemY *= 2;
    
    // 갈 수 있는 곳 표시
    rectangle.forEach(([x1, y1, x2, y2]) => {
        for (let x = x1; x <= x2; x++) {
            for (let y = y1; y <= y2; y++) {
                // 현재 rectangle의 둘레인 경우
                if (x === x1 || x === x2 || y === y1 || y === y2) {
                    // 겹치지 않은 경우
                    if (board[y][x] === 0) {
                        board[y][x] = 1;
                    }
                } else {
                    // rectanlge 내부
                    board[y][x] = 2;
                }
            }
        }
    })
    // board 확인
    // const a = board.map(e => e.join('')).join('\n')
    // console.log(a)
    // bfs순회하며 target을 찾는다
    const queue = [{r: characterY, c: characterX, count: 0}];
    board[characterY][characterX] = 0; // 시작점 방문표시
    const dr = [-1, 0, 1, 0];
    const dc = [0, 1, 0, -1];
    while(queue.length) {
        const curr = queue.shift();
        // 목표점 찾음
        if (curr.r === itemY && curr.c === itemX) {
            return curr.count/2; // !! 주의
        }
        
        for (let i = 0; i < 4; i++) {
            const nextR = curr.r + dr[i];
            const nextC = curr.c + dc[i];
            if (board[nextR][nextC] === 1) {
                board[nextR][nextC] = 0; // 방문표시
                queue.push({r: nextR, c: nextC, count: curr.count +1});
            }
        }
    }
    return answer;
}