백준) 17204 - 죽음의 게임

📌 문제 링크

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

---

📌 문제 탐색하기

• The Game of Death라고 불리는 죽음의 술게임을 할 때 친구가 걸리게 하려면 몇 번을 외쳐야 하는지 출력해라
• 말해야하는 가장 작은 양의 정수를 출력하며 어떤 방법으로도 친구가 걸리지 않는다면 -1을 출력해라
• 게임의 룰은 아래와 같다
  • N명의 사람들은 원탁에 둘러앉게 된다.
  • 게임을 시작하는 사람은 0번, 그 오른쪽 사람은 1번, 그 오른쪽은 2번, N-1번의 오른쪽 사람은 다시 0번이 된다.
  • 0번이 "신난다! 아싸 재미난다! 아싸 더 게임 오브 데! 스!" 라고 외침과 동시에, 모든 사람들은 각각 테이블에 둘러 앉은 사람들 중 한 명을 지목한다. 그리고 나서 0번은 임의의 양의 정수 M을 외친다.
  • 그 다음, 0번은 "1"이라고 말한다. 이때 "1"이라고 말한 사람이 지목한 사람은 "2"라고 말하고, "2"라고 말한 사람이 지목한 사람은 "3"이라고 말하고, 같은 방식으로 반복해 M까지 말하게 된다.
  • 이때 마지막으로 M이라고 말한 사람이 지목한 사람은 벌주를 마시게 된다.
  • 게임을 제안한 사람은 자연스럽게 0번이 된다.

시간복잡도

• 각 노드를 한 번씩만 방문하기 때문에 O(n)

알고리즘 선택

• DFS

---

📌 코드 설계하기

1. 문제의 입력값을 `info`와 `input`배열로 받아옵니다.
2. `info`를 띄어쓰기로 분리하여 게임에 참여하는 사람의 수 `n` 와 보성이의 번호 `bosung`를 가져옵니다.
3. `input`배열을 숫자로 변환합니다.
4. 게임에 참여하는 사람의 수 `n` 만큼 `visited` 배열을 선언하고 값을 `false`로 채워줍니다.
5. 현재 위치를 나타낼 `current`변수와 몇 번째 차례인지를 나타낼 `count`를 초기화합니다.
6. 아직 방문하지 않은 사람에 도달할 때까지 반복문을 돕니다.
   1. 현재 위치를 방문했다고 표시합니다.
   2. 카운트를 증가시킵니다.
   3. 현재 위치가 친구라면 정답을 출력하고 종료합니다.
   4. 다음 사람으로 이동합니다.
7. 반복문을 다 돌았음에도 친구를 찾지 못했다면 `-1`을 출력합니다.

---

📌 정답 코드

//https://www.acmicpc.net/problem/17204
export {};

const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input1.txt";
const [info, ...input] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");
const [n, bosung] = info.split(" ").map(Number);
const arr = input.map(Number);
const visited = new Array(n).fill(false);
let current = 0;
let count = 0;

while (!visited[current]) {
  visited[current] = true;
  count++;

  if (current === bosung) {
    console.log(count - 1);
    process.exit(0);
  }
  current = arr[current];
}
console.log(-1);