프로그래머스 - 아이템 줍기 (위클리 챌린지 11주차)

1. 문제

문제 링크

설명

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

지형은 각 변이 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 이하인 자연수입니다.
  • 지형을 나타내는 다각형 테두리 위의 한 점이 주어집니다.
• 캐릭터와 아이템의 처음 위치가 같은 경우는 없습니다.

입출력 예

rectangle	characterX	characterY	itemX	itemY	result
[[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]]	1	3	7	8	17
[[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]]	9	7	6	1	11
[[1,1,5,7]]	1	1	4	7	9
[[2,1,7,5],[6,4,10,10]]	3	1	7	10	15
[[2,2,5,5],[1,3,6,4],[3,1,4,6]]	1	4	6	3	10

2. 풀이

잡담
위클리 챌린지가 벌써 11주차... 거의 3개월이 지났다는 사실이 믿기시나요?
정말 시간이 빨리 흐르는 듯합니다.
이렇게 한 번씩 세월을 체감할 때마다
지나간 세월을 후회하지 않으려면 하루하루 알차게 살아야겠다고 늘 느낍니다.

본 풀이
오늘도 위클리 챌린지 11주차를 풀어보겠습니다.
이번엔 좀 어려운 문제가 출제돼서 조회수가 얼마나 끌릴지 기대됩니다. ㅎㅎ

계획1 - 좌표마다 알맞은 포인트 저장

아래 사진과 같이

• 각 사각형의 꼭지점과, 사각형끼리의 교차점은 코너 포인트
• 사각형 내부의 테두리는 블락 포인트
• 사각형 테두리는 보더 포인트

를 찍어줍니다.

우리는 캐릭터를 이동시킬 때 해당 좌표에 저장된 포인트의 값에 따라 이동을 정의할 겁니다.

• 보더 포인트 - 현 방향 유지하며 그대로 이동
• 코너 포인트 - 꺾을 방향을 탐색한 후, 그 방향으로 이동

이렇게만 움직이면 캐릭터를 아이템이 있는 곳으로 움직일 수 있습니다.

"그럼 블락 포인트는 어따 써먹는데?" 라는 의문이 나올 수 있는데요.
각각 사각형의 테두리에 보더 포인트를 저장하지 않는 용도로 쓰입니다.
위 사진과 같이 현재 사각형의 테두리가 다른 사각형의 내부에 있다면 보더 포인트를 찍으면 안됩니다.
만약 찍는다면 캐릭터가 사각형을 뚫고 지나가는 대참사가 일어납니다.

계획2 - 좌표를 두 배로 확대하기

왼쪽 이미지는 우리가 기대한 캐릭터의 이동 경로
오른쪽 이미지는 컴퓨터가 이동할 수 있는 이동 경로입니다.
이 부분을 해결하려면 저는 '좌표를 두 배로 확대하면 되겠다'라고 생각했습니다.
좌표를 두 배로 키움으로써 위 사진과 같은 문제 뿐만 아니라,
예시2와 같이 4개의 사각형 사이의 빈 공간으로 이동하는 문제 또한 해결할 수 있습니다.
너비가 1인 사각형 4개가 내부의 빈 공간을 만드는 경우, 캐릭터는 빈 공간으로 이동할 수 있게 되지만
좌표를 두 배로 키워버리면 각 사각형의 내부는 블락 포인트로 채워지니
그 사이의 빈 공간으로는 이동할 수 없어집니다.
그 외에도 많은 문제 사항이 있지만 좌표를 두 배로 확대함으로써 모두 해결이 가능합니다.

이 부분이 이 문제의 핵심 아닐까 싶습니다.
저는 처음에 문제가 하나씩 나올 때마다 if문으로 해결하려 했지만,
문제가 한 두 개가 아니란 사실을 깨닫고 과감히 기존 if문을 다 버리고
좌표를 두 배로 확장하는 로직으로 변경했습니다.
알고리즘이든, 실무에서든 항상 깨닫는 사실이지만
주먹구구식으로 예외처리를 하는 상황이 생기면 기존 로직을 과감히 버리고
모든 상황을 커버할 수 있는 새로운 로직을 고안해야 합니다.

이제 계획1에서 정의한대로 캐릭터를 이동시키면 됩니다.

3. 전체 코드

function solution(rectangle, characterX, characterY, itemX, itemY) {
    const MAX = 120;
    const moves = [[-1 ,0], [0, 1], [1, 0], [0, -1]];
    const POINTS = {
        EMPTY: 0, 
        BORDER: 1,
        CORNER: 2,
        BLOCK: 3,
        TARGET: 4,
    };
    const map = [...Array(MAX)].map(() => [...Array(MAX)].map(() => POINTS.EMPTY));

    // 블락일 땐 블락, 빈 값일 땐 보더, 보더일 땐 코너
    const getBorderPoint = (val) => (val == POINTS.BLOCK ? POINTS.BLOCK : val == POINTS.EMPTY ? POINTS.BORDER : POINTS.CORNER);

    rectangle.forEach(([x1, y1, x2, y2]) => {
        // 좌표 두 배 확대
        x1 *= 2; 
        y1 *= 2; 
        x2 *= 2;
        y2 *= 2;

        // 테두리는 블락 or 보더
        // 테두리 안쪽은 블락으로 칠하기
        for (let y = y1 + 1; y < y2; y++) {
            map[y][x1] = getBorderPoint(map[y][x1]);
            map[y][x2] = getBorderPoint(map[y][x2]);
            map[y][x1 + 1] = map[y][x2 - 1] = POINTS.BLOCK;
        }

        for (let x = x1 + 1; x < x2; x++) {
            map[y1][x] = getBorderPoint(map[y1][x]);
            map[y2][x] = getBorderPoint(map[y2][x]);
            map[y1 + 1][x] = map[y2 - 1][x] = POINTS.BLOCK;
        }

        // 꼭지점 코너로 칠하기
        map[y1][x1] = POINTS.CORNER;
        map[y2][x1] = POINTS.CORNER;
        map[y1][x2] = POINTS.CORNER;
        map[y2][x2] = POINTS.CORNER;
    });

    itemY *= 2;
    itemX *= 2;
    characterY *= 2;
    characterX *= 2;
    map[itemY][itemX] = POINTS.TARGET;
    map[characterY][characterX] = POINTS.BLOCK;

    let ans = Number.MAX_SAFE_INTEGER;

    // 현 캐릭터 위치에서 4방향 탐색
    for (let dir = 0; dir < 4; dir++) {
        let y = characterY + moves[dir][0];
        let x = characterX + moves[dir][1];

        if (map[y][x] != POINTS.CORNER && map[y][x] != POINTS.BORDER) continue;

        let curDir = dir;
        let count = 1;

        // 타겟을 만날 때까지 이동
        while (map[y][x] != POINTS.TARGET) {
            // 코너일 땐 방향 전환
            if (map[y][x] == POINTS.CORNER) {
                for (let candDir = 0; candDir < 4; candDir++) {
                    // 현 방향이나, 반대 방향은 넘어가기
                    if ([curDir, (curDir + 2) % 4].includes(candDir)) continue;

                    const ny = y + moves[candDir][0];
                    const nx = x + moves[candDir][1];

                    if (ny < 0 || ny >= MAX || nx < 0 || nx >= MAX) continue;

                    if (![POINTS.EMPTY, POINTS.BLOCK].includes(map[ny][nx])) {
                        curDir = candDir;
                        break;
                    }
                }
            }

            map[y][x] = POINTS.BLOCK;
            y += moves[curDir][0];
            x += moves[curDir][1];
            count++;
        }

        ans = Math.min(ans, count);
    }

    // 좌표를 두 배로 확대했으니 정답은 절반으로 나누기
    return ans / 2;
}

4. 회고

지금 생각이 든 사실인데, 코너 포인트를 찍을 필요 없이
캐릭터 위치에서 BFS를 돌리는 게 더 간단할 듯 합니다.