[JS] 백준 16928: 뱀과 사다리 게임

https://www.acmicpc.net/problem/16928

 

// 16928 뱀과 사다리 게임

// 그래프, 너비우선탐색
/* 설계


1. 둘째줄부터 마지막줄까지 graph에 넣어. 
(graph는 101으로 선언한다음에 줄의 첫번째 원소값을 인덱스로 줄의 두번째 원솟값을 값으로 넣어)


2. let 현재위치와 횟수값 = [1, 0];으로 초기화해. queue=[]도 초기화한 다음에 현재 위치를 push 해.
(여기서 shift연산을 사용하지 않기 위해 인덱스 포인터를 활용할거야.)
let pointer = 0;
const visited도 101배열 그리고 모든 원소의 값을 false 값으로 초기화해.
visited[1] = true;

3. while (pointer < queue.length)
3.1 queue의 가장 앞의 값을 가져와. 현재위치, 현재 카운트
3.1.1 pointer를 갱신해. pointer++
3.1.2 현재 위치가 100이라면 return count를 반환해.
3.2 for문을 돌면서 주사위의 값이 1부터 6인 경우 값을 현재위치 값을 그에 맞게 더해서 갱신해
3.2.1 새로 갱신된 값이 100이하인지 확인하고 100 초과되었다면 continue (엣지 케이스)
3.2.2.새로 갱신된 값이 graph에 있는지 확인해 (인덱스로 접근해서 값이 있으면 그 값으로 갱신돼)
3.2.3. visited[갱신된 현재위치] 값이 false라면
visited[갱신된 현재위치] = true;
그러고 나서 [갱신된 위치, count+1]를 queue에 push해
*/

const input = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .replaceAll("\r", "") // just in case
  .trim()
  .split("\n");

/**
 * 게임판의 상태가 주어졌을 때, 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값
 * @param {string[]} input
 * @returns {string} 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값
 */
function solution(input) {
  const [N, M] = input[0].split(" ").map(Number);
  const graph = Array.from({ length: 101 }, (_, i) => i);

  for (let line = 1; line <= N + M; line++) {
    const [first, last] = input[line].split(" ").map(Number);
    graph[first] = last;
  }

  const visited = Array(101).fill(false);
  visited[1] = true;

  const queue = [];
  let pointer = 0;

  queue.push([1, 0]); // 현재위치와 횟수

  while (pointer < queue.length) {
    const [currentPos, currentCount] = queue[pointer];
    pointer++;

    if (currentPos === 100) {
      return currentCount;
    }

    for (let i = 1; i <= 6; i++) {
      const nextDicePos = currentPos + i;

      if (nextDicePos > 100) continue;

      const nextPos = graph[nextDicePos];

      if (!visited[nextPos]) {
        visited[nextPos] = true;
        queue.push([nextPos, currentCount + 1]);
      }
    }
  }
}

const result = solution(input);
console.log(result);

 

설계하면서 궁금한 점

1. 이 문제는 왜 너비우선탐색을 활용해야 될까?

1. 가중치가 동일하다.

말하자면 주사위 1부터 6까지 굴려서

다음 위치를 갱신하는 것(뱀과 사다리로 이동하는 것 포함)에 대한 횟수가 모두 1회이다.

2. 최단거리를 묻고 있다.

 

추가로) 그렇다면 왜 이게 깊이우선탐색을 사용하면 안되는 것일까?

깊이우선탐색을 해서 가장 먼저 100에 도착한 것이 항상 최단거리는 아니다.

그렇다면 모든 거리를 탐색해서 최단거리를 구한다면 시간 초과가 발생한다. (효율적이지 않다.)

 

참고) 그래프 탐색의 기본 뼈대 = '주머니'에 노드를 넣고 하나씩 빼면서 확인

1. BFS : 주머니 = queue

원리: 가장 가까운 노드를 주머니의 '맨 앞'에서 뺀다. FIFO

결과: 거리가 1, 2, 3인 순서대로 탐색 (최단 거리 보장)

 

2. DFS : 주머니 = 스택

원리: 가장 최근에 발견한 노드(깊은 노드)를 주머니의 '맨 위'에서 먼저 뺀다. LIFO

결과: 길이 막힐 때까지 한 우물만 깊게 파고들어 감. 백트래킹 가능

 

3. 다익스트라 알고리즘 : 주머니 = 우선순위 큐

원리: 가중치(거리/비용)가 가장 작은 노드부터 주머니에서 먼저 뺀다.

결과: 간선의 비용이 제각각 다를 때의 최단 경로

 

4. 0-1 BFS : 주머니 = 덱

원리: 가중치가 0인 간선은 덱의 맨 앞, 가중치가 1인 간선은 맨 뒤에 넣는다.

결과: 가중치가 0과 1로만 이루어진 특수한 맵에서 다익스트라보다 훨씬 빠르게 최단경로 도출(O(N))

 

2. Array.from vs Array(N).fill()의 V8 엔진 내부 동작 차이

1. Array.from({length: 101}, () => false);
() => false라는 익명함수(콜백함수)를 101번 실행

 

2. Array(101).fill(false);

1) 힙 메모리에 101칸짜리 연속된 빈공간 할당.

2) .fill()은 V8 엔진 내부의 C++로 최적화된 빌트인 함수를 호출

-> 연속된 메모리 공간에 원시값을 한번에 덮어씌우는 방식

(Block memory fill.

1. 워드 단위(8바이트) 쓰기. 일반적인 for문은 1바이트씩 처리한다.

2. SIMD 하나의 명령어로 여러 데이터를 동시에 처리

CPU의 벡터 레지스터에 초기화할 값들을 가득 채운 뒤, 단 한 번의 명령어로 덮어씌운다.

여기서 SIMD는 완벽하게 동일한 데이터만 복사할 수 있기에

배열과 같은 참조 주소값은 참조 주소값들로 가득 채워지기 때문에 얕은 복사가 된다.)

 

따라서 모든 원소를 동일한 원시값 하나로 덮어씌운다면 -> Array(N).fill()

(원시타입: Number, String, Symbol, undefined, null, BigInt, Boolean)

(참조타입은 한 번 만들고 나머지는 주소값 복사 즉 얕은 복사를 하므로 X) 

각기 다른 값을 넣어야 하는 경우 -> Arrary.from