[백준 16928] 뱀과 사다리 게임 with Node.js

문제 링크

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

16928번: 뱀과 사다리 게임

풀이

const solve = (input) => {
  input.shift();
  const temp = [...new Array(101)].map((_, i) => i);
  for (const i of input) {
    const [ start, end ] = i.split(' ').map(v => +v);
    temp[start] = end;
  }
  const graph = [...new Array(101)]
    .map((_, i) => [...new Array(6)]
      .map((_, ii) => temp[i + ii + 1])
      .filter(v => v <= 100)
    );
  console.log(BFS(1, graph));
};

const BFS = (start, graph) => {
  const visited = new Array(101).fill(false);
  const queue = [[start, 0]];
  while (queue.length) {
    const [ node, count ] = queue.shift();
    if (node === 100) return count;
    if (!visited[node]) {
      visited[node] = true;
      queue.push(...graph[node].map(v => [v, count + 1]));
    }
  }
}

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
solve(input);

각 칸들의 관계를 그래프로 나타내야 한다.

 

예를 들어 1번 칸은 주사위를 굴려서 갈 수 있는 2, 3, 4, 5, 6, 7번 칸과 연결되어 있다.

만약 6번 칸에서 사다리가 시작되어 20번 칸으로 연결되어 있다면,

1번 칸은 2, 3, 4, 5, 7, 20번 칸과 연결되어 있는 것이다.

 

뱀의 경우에도 마찬가지다.

예를 들어 20번 칸은 주사위를 굴려서 갈 수 있는 21, 22, 23, 24, 25, 26번 칸과 연결되어 있다.

만약 21번 칸에서 뱀이 시작되어 10번 칸으로 연결되어 있다면,

20번 칸은 10, 22, 23, 24, 25, 26번 칸과 연결되어 있는 것이다.

 

여기서 주의할 점은 1번 칸에서 20번 칸으로 가는 과정이 1 → 6 → 20이 아니라 곧장 1 → 20 이라는 점이다.

즉, 주사위를 두 번 굴리는 것이 아닌, 한 번 굴려서 1번 칸에서 20번 칸으로 갈 수 있다는 뜻이다.

따라서, 6번 칸은 그 어떤 칸에서도 접근할 수 없는 고립된 칸이고,

6번 칸과 연결되는 다른 칸들은 모두 20번 칸으로 연결되는 것으로 간주해야 한다.

 

뱀의 경우도 마찬가지로 20번 칸에서 10번 칸으로 가는 과정은 20 → 21 → 10이 아니라 20 → 10이다.

주사위를 한 번 굴려서 1이 나오면 21이 아닌 10으로 가게 되는 것이다.

 

이러한 사다리와 뱀의 시작칸에 연결된 칸들을 도착칸으로 바로 연결시키기 위해 temp 배열을 만들고,

기본적으로 temp[index] = index이나, temp['사다리/뱀의 시작칸'] = '사다리/뱀의 도착칸'으로 바꿔준다.

그리고 나서 graph의 각 인덱스에는 해당 칸과 연결된 칸들의 배열을 저장한다.

 

graph는 아래와 같이 저장된다.

// 사다리가 6번 칸에서 시작해서 20번 칸으로 가고,
// 뱀이 21번 칸에서 시작해서 10번 칸으로 간다고 가정

[
  [ 1, 2, 3, 4, 5, 6 ], // 인덱스를 맞추기 위해 있는 0번째 칸. 의미 없음.
  [ 2, 3, 4, 5, 20, 7 ], // 1번 칸
  [ 3, 4, 5, 20, 7, 8 ],
  [ 4, 5, 20, 7, 8, 9 ],
  [ 5, 20, 7, 8, 9, 10 ],
  [ 20, 7, 8, 9, 10, 11 ],
  [ 7, 8, 9, 10, 11, 12 ],
  [ 8, 9, 10, 11, 12, 13 ],
  [ 9, 10, 11, 12, 13, 14 ],
  [ 10, 11, 12, 13, 14, 15 ],
  [ 11, 12, 13, 14, 15, 16 ],
  [ 12, 13, 14, 15, 16, 17 ],
  [ 13, 14, 15, 16, 17, 18 ],
  [ 14, 15, 16, 17, 18, 19 ],
  [ 15, 16, 17, 18, 19, 20 ],
  [ 16, 17, 18, 19, 20, 10 ],
  [ 17, 18, 19, 20, 10, 22 ],
  [ 18, 19, 20, 10, 22, 23 ],
  [ 19, 20, 10, 22, 23, 24 ],
  [ 20, 10, 22, 23, 24, 25 ],
  
  ...
  
  [98, 99, 100],
  [99, 100]
  [100],
  [] // 100번 칸
]

이제 이 graph에서 BFS로 최단거리를 구하면 주사위를 굴리는 최소 횟수를 구할 수 있다.

BFS는 100에 처음으로 도착할 때까지 너비우선탐색을 실행하고,

100에 도달하면 start칸(1번 칸)에서부터 100번 칸까지 이동한 횟수를 반환한다.