[코테 꿀팁] BFS 사용 중 시간 초과에 걸린다면? with. JS, 백준 12851번

백준 12851번 숨바꼭질2 문제를 풀다가 발생한 문제입니다. 맞는 풀이인데 시간 초과가 발생해서 살펴본 결과 원인을 찾았습니다.

 

▼시간 초과가 발생한 코드

const [n, k] = require("fs")
  .readFileSync("dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map(Number);
// bfs > 이동 방향이 x-1, x+1, 2*x로 바뀐
const MAX = 200000
const visited = new Array(MAX+1).fill(0);
const cnt = new Array(MAX+1).fill(0);
const bfs = (s) => {
  const q = [s];

  visited[s] = 1;
  cnt[s] = 1;
  while (q.length) {
    const p = q.shift();
    const n = [p + 1, p - 1, p * 2];
      
    for (let next of n) {
      if (0 <= next && next <= MAX*2) {
        if (!visited[next]) {
          q.push(next);
          visited[next] = visited[p] + 1;
          cnt[next] += cnt[p];
        } else if (visited[next] == visited[p] + 1) {
          cnt[next] += cnt[p];
        }
      }
    }
  }

  console.log(visited[k] - 1);
  console.log(cnt[k]);
};

if (n == k) {
  console.log("0");
  console.log("1");
} else {
  bfs(n);
}

 

▼시간 초과 발생하는 것으로 예상되는 부분

while (q.length) {
  const p = q.shift(); // 1. 큐를 구현하지 않고 배열의 shift()를 이용한 부분
  const n = [p + 1, p - 1, p * 2]; // 2. 배열을 생성하고 계산한 값을 넣는 부분

  for (let next of n) { // 3. 기존 for문이 아닌 for of 문을 사용한 부분
    if (0 <= next && next <= MAX*2) {
      if (!visited[next]) {
        q.push(next);
        visited[next] = visited[p] + 1;
        cnt[next] += cnt[p];
      } else if (visited[next] == visited[p] + 1) {
        cnt[next] += cnt[p];
      }
    }
  }
}

 

▼시간 초과가 해결된 코드3 - 1번 오류 예상 부분 수

class QUEUE { // 큐를 클래스로 정의
    constructor() {
        this.q = {};
        this.front = 0;
        this.rear = 0;
    }
    
    size() {
        return this.rear - this.front;
    }
    
    enqueue(item) {
        this.q[this.rear++] = item;
    }
    
    dequeue() {
        if(this.size() == 0) {
            return null;
        }
        const data = this.q[this.front];
        
        delete this.q[this.front++];
        
        return data;
    }
}
// ...
const bfs = (s) => { // 큐 클래스 사용하는 방식으로 다시 구현
  const q = new QUEUE;
  q.enqueue(s);

  visited[s] = 1;
  cnt[s] = 1;
  while (q.size()) {
    const p = q.dequeue();
    const n = [p + 1, p - 1, p * 2];
      
    for (let next of n) {
      if (0 <= next && next <= MAX*2) {
        if (!visited[next]) {
          q.enqueue(next);
          visited[next] = visited[p] + 1;
          cnt[next] += cnt[p];
        } else if (visited[next] == visited[p] + 1) {
          cnt[next] += cnt[p];
        }
      }
    }
  }
// ...

 

▼시간 초과가 해결된 코드1 - 3번 오류 예상 부분 수정

객체를 사용한 큐나 배열을 사용한 경우 메모리 차이는 크지 않지만, 배열의 shift 연산이 시간을 많이 사용하는 것을 확인할 수 있습니다.

// for...of 문을 for문으로 변경
while (q.length) {
  const p = q.shift();
  const n = [p + 1, p - 1, p * 2];

  for (let i=0; i<3; i++) {
      const next = n[i];
    if (0 <= next && next <= MAX*2) {
      if (!visited[next]) {
        q.push(next);
        visited[next] = visited[p] + 1;
        cnt[next] += cnt[p];
      } else if (visited[next] == visited[p] + 1) {
        cnt[next] += cnt[p];
      }
    }
  }
}

 

▼시간 초과가 해결된 코드2 - 2,3번 오류 예상 부분 수

해당 결과를 살펴봤을 때 배열을 사용하거나 객체로 만든 큐를 사용하는 경우 메모리가 상당히 사용되는 것을 확인할 수 있습니다.

// for...of문을 for문으로 변경
// 배열과 계산하는 부분을 if...else문으로 변경
while (q.length) {
  const p = q.shift();
  
  for (let i = 0; i < 3; i++) {
    let next;
    if (i === 0) next = p * 2;
    else if (i === 1) next = p + 1;
    else next = p - 1;

    if (0 <= next && next <= MAX*2) {
      if (!visited[next]) {
        q.push(next);
        visited[next] = visited[p] + 1;
        cnt[next] += cnt[p];
      } else if (visited[next] == visited[p] + 1) {
        cnt[next] += cnt[p];
      }
    }
  }
}

 

해당 문제는 BFS로 많은 경우의 수를 방문하는 케이스입니다. 이처럼 많은 경우의 수를 방문하는 경우 사소한 시간 차이가 중요합니다. 그렇기 때문에 주어진 시간이 여유롭지 않거나 시간 초과가 발생한다면 조금이라도 시간이 적게 걸리는 방법을 택해야 합니다.

 

문제를 해결했다고 생각했었는데 다시 살펴보니 실제 문제가 있던 부분은 다른 부분이었습니다...😭

 

▼뻘쭘하지만 실제 문제가 있던 부분

while (q.length) {
  const p = q.shift();
  const n = [p + 1, p - 1, p * 2];

  for (let next of n) {
    if (0 <= next && next <= MAX*2) { // 진짜 문제는 MAX를 200,000으로 해놓고 *2를 했다...
      if (!visited[next]) {
        q.push(next);
        visited[next] = visited[p] + 1;
        cnt[next] += cnt[p];
      } else if (visited[next] == visited[p] + 1) {
        cnt[next] += cnt[p];
      }
    }
  }
}

 

*2를 지우고 나니 맨 처음 오류가 났다고 생각한 코드를 포함한 모든 코드가 잘 동작했습니다. (결과 이미지를 클릭하면 코드를 보실 수 있습니다)

▲ 처음 시도했다가 오류난 코드 재실행 결과

▲ 1번 오류 수정한 코드 재실행 결과

▲ 3번 오류 수정한 코드 재실행 결과

▲ 2,3번 오류 수정한 코드 재실행 결과

▲ 1,2,3 오류 수정한 코드 재실행 결과

 

다시 결과를 살펴보니 메모리와 시간이 대폭 감소했습니다... 다음부터는 문제를 잘 살펴봐야겠습니다.

 

추가적으로 객체를 사용한 큐를 사용하면 메모리가 많이 사용되는 것으로 보여 크기가 정해진 배열을 사용한 순환 큐를 사용해 봤습니다. 결과는 메모리와 시간 모두 단축된 것을 확인할 수 있었습니다.

▲ 순환 큐 코드 실행 결과

 

결과를 살펴보니 어이가 없었지만 그래도 사소한 시간 차이가 중요하다는 사실을 깨달았다는 것을 하나 배워갑니다... 가치 있는 시간이었습니다.