[Javascript] 프로그래머스 - 아이템 줍기

목차

1. 문제 풀이

  1) 테두리 구하기

  2) 테두리 이동할 때, 풀이법 (❌ 주의: 칸 이동과 다름)

2. 전체 코드

3. 느낀 점

---

1. 문제 풀이

그림과 같이 여러 다각형이 배열 형태로 주어질 때, 테두리 정보를 배열에 저장해두어야 한다.

출발지 (x, y) 에서 목적지 (x, y) 에 도달할 때까지 걸리는 가장 짧은 거리를 계산하기 위해서는 bfs 코드를 수행한다.

 

직사각형 입력 형식

직사각형 배열은 [fromX, fromY, toX, toY] 로 주어지며, 각각 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점 정보이다.

예를 들어, 가장 아래의 직사각형은 [1,1,7,4] 로 주어진다.

 

처음 생각한 방식

처음에 생각한 방식은 직사각형이 주어질 때, 모든 선분을 1로 만드는 것이였다.

그리고 1과 0(초기화) 경계에 있는 부분을 다시 계산하여 테두리를 구하는 방법이였다.

이렇게 구현하려고 하니, 경계 부분을 찾는 부분 구현이 만만치 않아 다른 블로그를 찾아 해결할 수 있었다.

 

1️⃣ 테두리 구하기 

직사각형의 테두리는 다음과 같이 구할 수 있다.

x == fromX 이거나 x == toX 이거나 y == fromY 이거나 y == toY 

따라서 테두리와 아닌 것을 구분하기 위하여, 위의 경우는 1로 초기화, 아닌 경우는 -1로 초기화한다.

 

이 때, 이미 처리한 선분의 경우 다시 1로 설정을 하면 안되는데, 이유는 아래의 그림과 같다.

 

따라서 이를 코드를 나타내면 다음과 같다.

2️⃣ 테두리 이동할 때 풀이법 

결론부터 얘기하자면 모든 좌표에 x2를 해주어야 한다.

그 이유는 지금부터 자세히 설명할 수 있다.

 

기존 칸의 이동같은 경우는 4가지의 방향(상, 하, 좌, 우)로 이동하되, 유효한 경우(ex. 1인경우) 이동하면 된다.

하지만 테두리의 경우는 약간 복잡한다.

 

기존 칸의 이동

오렌지색 칸 → 옐로우 칸 이동 시에 +1 칸 증가이다. 

 

테두리의 이동

노란색 테두리의 경우를 보면 점프해서 지나갈 수 없지만, 배열에서 모두 1로 설정되어있으므로 지나갈 수 있게 된다.

따라서 이 지점에서 가지 못하게 막아야 해야 한다.

 

모든 좌표에 x2를 하므로써, 모양은 같으면서 사이에 선분이 하나 더 생기게 된다.

 

또한 모든 좌표에 x2를 했기 때문에, 나중에 최소 거리를 구할 때도 x2 된 값이 나온다.

따라서 그 거리 / 2를 하면 정답이 나온다.

---

2. 전체 코드

DOUBLE_MAX = 103;

function solution(rectangle, characterX, characterY, itemX, itemY) {
    characterX *= 2;
    characterY *= 2;
    itemX *= 2;
    itemY *= 2;
    
    var map = Array.from({length: DOUBLE_MAX}, ()=> Array(DOUBLE_MAX).fill(0));
    var doubleRect = rectangle.map((rect)=> rect.map(v=> v * 2));
    
    var dx = [1,0,-1,0];
    var dy = [0,-1,0,1];
    
    var maps = doubleRect.forEach(([fromX, fromY, toX, toY])=> {
        for (let x = fromX; x <= toX; x++) {
            for (let y = fromY; y <= toY; y++) {
                if (x == fromX || x == toX || y == fromY || y == toY) {
                    if (!map[x][y]) {
                        map[x][y] = 1;
                    }
                } else {
                    map[x][y] = -1;
                }
            }
        }
    })
    
    // bfs
    var q = [[characterX, characterY]];
    while (q.length) { 
        var [curX, curY] = q.shift(); 
        
        if (curX === itemX && curY === itemY) {
            break;
        }
        
        for (let i = 0; i < 4; i++) { 
            var nextX = curX + dx[i]; 
            var nextY = curY + dy[i];
            
            if (0 <= nextX && nextX < DOUBLE_MAX && 0 <= nextY && nextY < DOUBLE_MAX) {
                if (map[nextX][nextY] == 1) {
                    map[nextX][nextY] = map[curX][curY] + 1;
                    q.push([nextX, nextY]);
                }
            }
        }
    }

    
    return (map[itemX][itemY] -1) / 2;
}

 

 

---

3. 느낀 점

다른 문제보다 좀 더 많이 얻어갈 수 있는 문제였던 것 같다.

추가적으로 나중에 이 코드를 다시 보게된다면 시간 복잡도를 확실하게 계산해야겠다.

- BFS (모든 노드를 순회) : O(N)

- shift 연산 : O(N)

여기에 N 대신 2차원 좌표니깐 N^2를 넣어서 총 O(N^4) 이라고 계산했는데, 왜 ChatGPT는 O(N^3)이라고 하는지 모르겠다.

오늘은 여기까지....미래의 나에게 맡기자

---