문제

중앙대학교 소프트웨어대학 새내기들을 맞이하게 된 17학번 김영기는 두 학번이라는 차이를 극복하기 위해 새내기들과 친해지려고 노력하고 있다. 그 노력 중 하나는 바로 새내기들과의 술자리에 참여하는 것이다. 그러나 혼자 가기에 민망했던 영기는 동기 보성이를 꼬셔 같이 술자리에 참석했다. 새내기들과 같이 술을 마시게 된 영기와 보성이는 분위기가 가라 앉을 때쯤 The Game of Death라고 불리는 죽음의 술게임을 제안한다.

죽음의 게임의 룰은 간단하다.

게임에 참여하는 N명의 사람들은 원탁에 둘러앉게 된다. 게임을 시작하는 사람은 0번, 그 오른쪽 사람은 1번, 그 오른쪽은 2번, N-1번의 오른쪽 사람은 다시 0번이 된다.

0번이 "신난다! 아싸 재미난다! 아싸 더 게임 오브 데! 스!" 라고 외침과 동시에, 모든 사람들은 각각 테이블에 둘러 앉은 사람들 중 한 명을 지목한다. 그리고 나서 0번은 임의의 양의 정수 M을 외친다.

그 다음, 0번은 "1"이라고 말한다. 이때 "1"이라고 말한 사람이 지목한 사람은 "2"라고 말하고, "2"라고 말한 사람이 지목한 사람은 "3"이라고 말하고, 같은 방식으로 반복해 M까지 말하게 된다. 이때 마지막으로 M이라고 말한 사람이 지목한 사람은 벌주를 마시게 된다.

새내기에게 벌주를 마시게 하기에는 죄책감이 들었던 영기는 동기인 보성이를 공격하기로 결심했다. 게임 참여자들간에 지목을 완료한 상태가 주어질때, 보성이가 벌주를 마시기 위해 영기가 불러야 하는 가장 작은 양의 정수 M을 보성이 몰래 귀띔해 주도록 하자.

김영기는 게임을 제안하였기에 자연스럽게 0번이 된다.

입력

첫 번째 줄에 게임에 참여하는 사람의 수 N(3 ≤ N ≤ 150)과 보성이의 번호 K(1 ≤ K ≤ N - 1)가 공백을 두고 주어진다.

두번째 줄부터 N줄에 걸쳐 i(0 ≤ i ≤ N - 1)번 사람이 지목하는 사람의 번호 ai(0 ≤ ai ≤ N - 1)가 주어진다. 자기 자신을 지목하는 경우도 존재할 수 있다.

출력

영기가 말해야 하는 가장 작은 양의 정수 M을 출력한다. 만약 어떤 방법으로도 보성이가 걸리지 않는다면 -1을 출력한다.

예제 입력

5 3
1
3
2
1
4

예제 출력

2

내가 했던 풀이 방법

1. Graph 클래스를 구현한다. 이에 대한 자세한 내용은 그래프에서 정리하였다.
2. graph에 0부터 N-1까지 node를 추가해준다.
3. i를 from으로 하고 i번째 사람이 지목한 사람의 번호를 to로 하여 Edge를 추가해준다.
4. current를 0으로 초기화해주고, visited를 N개의 boolean 배열로 만들어 false로 초기화해준다. current는 현재 지목된 사람이고, 게임은 항상 0번부터 시작하므로, 0으로 초기화해주었다. 0번은 지목당한 것과 같으므로 visited를 true로 바꾸어준다.
5. 보성이가 걸리지 않는 경우는 지목된 사람이 다시 지목되어 사이클을 형성하는 경우 뿐이다. 해당 게임은 한 명당 한 명밖에 지목을 할 수 없으므로, degree가 항상 1인 그래프이기 때문이다. 해당 경우 while문을 탈출해주어야 하므로, isImpossible 변수를 false로 초기화해준다.
6. current가 지목한 사람이 지목된 적이 없을 경우(visited[i]가 false인 경우) current를 i로 바꿔주고, visited를 true로 바꿔준다. 만약 지목된 사람이 지목된 적이 있는 경우 isImpossible을 true로 바꿔준다. 만약 isImpossible이 true면 while문을 탈출하고, false일 경우 M을 1 증가시켜준다. while문을 current가 K가 될 때까지 반복해준다.
7. while문을 탈출했을 때 isImpossible이 true일 경우, M을 -1로 바꿔준다.
8. M을 출력해준다.

코드

const fs = require('fs');
let [n, ...number] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

let N = Number(n.trim().split(' ')[0]);
let K = Number(n.trim().split(' ')[1]);

class Graph {
  constructor() {
    this.nodes = {};
  }

  addNode(node) {
    this.nodes[node] = this.nodes[node] || [];
  }

  removeNode(node) {
    if (this.contains(node)) {
      while (this.nodes[node].length > 0) {
        this.removeEdge(this.nodes[node][0], node);
      }
      delete this.nodes[node];
    }
  }

  contains(node) {
    return !!this.nodes[node];
  }

  addEdge(from, to) {
    if (!this.contains(from) || !this.contains(to)) return;
    if (!this.hasEdge(from, to)) this.nodes[from].push(to);
  }

  removeEdge(from, to) {
    if (!this.contains(from) || !this.contains(to)) return;
    if (this.hasEdge(from, to)) {
      const index = this.nodes[from].indexOf(to);
      this.nodes[from].splice(index, 1);
    }
  }

  hasEdge(from, to) {
    if (!this.contains(from)) return false;
    return !!this.nodes[from].includes(to);
  }
}

let graph = new Graph();
for (let i = 0; i < N; i++) {
  graph.addNode(i);
}
for (let i = 0; i < N; i++) {
  number[i] = Number(number[i].trim());
  graph.addEdge(i, number[i]);
}

let current = 0;
let M = 0;
let visited = new Array(N).fill(false);
visited[0] = true;
let isImpossible = false;
while (true) {
  if (current === K) break;
  for (let i = 0; i < N; i++) {
    if (graph.hasEdge(current, i) && !visited[i]) {
      current = i;
      visited[i] = true;
      break;
    } else if (graph.hasEdge(current, i) && visited[i]) {
      isImpossible = true;
    }
  }
  if (isImpossible) break;
  M++;
}

if (isImpossible) M = -1;

console.log(M);

회고

그래프만 구현했으면 쉽게 풀이할 수 있던 문제.