[Javascript] 프로그래머스 - 게임 맵 최단거리

목차

1. 문제 풀이

2. 내가 푼 정답 (shift 연산 사용)

3. 개선한 풀이 (큐 직접 구현)

---

1. 문제 풀이

2차원 평면에서 출발지점과 목적지점이 주어질 때, 장애물(0)을 이동하는 데 걸리는 최단 거리를 구하는 문제이므로, bfs로 해결할 수 있었다.

다만, 시간 복잡도를 줄이는 데에서 애를 먹었다.

 

시간 복잡도

제한 조건에서 알다시피 maps의 row, col은 최대 100이다. 따라서 row, col을 둘 다 N 이라고 하겠다.

이 때, 시간 복잡도는 다음과 같다.

시간 복잡도
- 모든 칸을 순회 : O(N^2)
- shift 연산 : O(N^2)
👉 O(N^4) 

최악의 경우
N <= 100이므로, O(100^4) 
👉 O(10^8)

 

여기서 문제였던 부분이 1초당 10^8 연산을 할 수 있는데, 그럼 간당간당하게 되거나 안되거나 하겠다. 라는 결론이 나왔다.

아니나 다를까 맨 처음 코드에서는 효율성 0점이 나왔고, 약간의 코드를 수정하니 됐다 안됐다 하다가

아래와 같은 식으로 약간 수정하니, 정답이 되었다.

 

1️⃣ 4가지 방향 (상, 하, 좌, 우) 

1. for (let i = 0; i < 4; i++) 방식

- 시간 복잡도 : O(1)

- 배열 인덱싱 방식

2. for (const [dr, dc] of directions) 방식

- 시간 복잡도 : O(1)

- 객체 분해 할당 방식

 

1과 2 비교

두 코드를 비교했을 때 이론적으로는 같은 시간 복잡도를 가지지만, 실제로는 배열 인덱싱 방식이 약간 더 빠르다.

특히 반복문 내에서 구조 분해 할당이 계속 발생하면, 메모리 접근, 할당 등 추가 비용이 발생하므로, 약간 더 느릴 수 있다고 한다.

👉 객체 분해 할당 방식 → 배열 인덱싱 방식으로 변환하여 약간의 시간을 줄일 수 있었다.

 

2️⃣ 방문표시 visited 배열의 유무

visited 배열을 추가하는 목적은 이미 방문한 곳을 다시 방문하지 않도록 하여 불필요한 연산을 방지하는 것이다.

하지만 기존 배열 maps 에 기록할 수 있기 때문에 visited를 추가하는 것은 낭비일 수 있다.

 

1. visited 썼을 때

아래 코드에서는 visited를 사용했지만, visited를 쓰지 않아도 방문 여부를 알 수 있다.

땅을 밟을 때마다 거리 = 이전 거리 + 1 로 갱신하는데,

결국 maps[x][y] 가 1일 경우, 방문 하지 않다라고 해석된다.

 

2. visited 안썼을 때

 

1과 2 비교

두 코드를 비교했을 때, 시간 복잡도는 같지만 visited 배열을 사용하므로써 추가적인 시간과 공간 비용이 발생한다.

시간이 충분히 여유 있을 경우, visited 배열을 사용하는 방식이 코드 관점에서는 직관적일 수는 있지만,

조금이라도 아끼기 위해서는 visited 배열 대신 maps만을 이용하는 것이 더 효율적이다.

---

2. 내가 푼 정답 코드

function solution(maps) {
    var row = maps.length; 
    var col = maps[0].length;
    var q = [[0,0]];
    
    var dr = [0,1,0,-1];
    var dc = [1,0,-1,0];

    while(q.length) { 
        var [r, c] = q.shift();
        
        for (let i = 0; i < 4; i++) { 
            var nextR = r + dr[i];
            var nextC = c + dc[i];
            
            if (0 <= nextR  && nextR < row && 0 <= nextC && nextC < col) {
                if (maps[nextR][nextC] == 1) { 
                    q.push([nextR, nextC]);
                    maps[nextR][nextC] = maps[r][c] + 1;
                }
            }
        }
    }
    
    return maps[row-1][col-1] === 1? -1: maps[row-1][col-1];
}

 

---

3. 개선한 풀이 (큐 직접 구현)

 

링크드리스트 개념을 이용하여, 직접 큐를 구현하였다.

알다시피, shift는 O(N)가 걸리는 데, 직접 구현하면 O(N) → O(1) 까지 줄일 수 있다. 

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.count = 0;
  }

  isEmpty() {
    return this.count === 0;
  }

  push(data) {
    const newNode = new Node(data);

    if (this.isEmpty()) {
      this.head = newNode;
    } else {
      this.tail.next = newNode;
    }

    this.tail = newNode;
    this.count++;
  }

  popleft() {
    if (this.isEmpty()) {
      return null;
    }

    const removeNode = this.head;
    this.head = this.head.next;

    if (this.count === 1) {
      this.tail = null;
    }

    this.count--;
    return removeNode.data;
  }
}

function solution(maps) {
    var row = maps.length; 
    var col = maps[0].length;
    var q = new Queue;
    q.push([0,0]);
    
    var dr = [0,1,0,-1];
    var dc = [1,0,-1,0];

    while(q.count) { 
        var [r, c] = q.popleft();
        
        for (let i = 0; i < 4; i++) { 
            var nextR = r + dr[i];
            var nextC = c + dc[i];
            
            if (0 <= nextR  && nextR < row && 0 <= nextC && nextC < col) {
                if (maps[nextR][nextC] == 1) { 
                    q.push([nextR, nextC]);
                    maps[nextR][nextC] = maps[r][c] + 1;
                }
            }
        }
    }
    
    return maps[row-1][col-1] === 1? -1: maps[row-1][col-1];
}

---