[BOJ-JS] 11558번 - The Game of Death

11558번: The Game of Death (acmicpc.net)

 

배열의 첫 번째 요소부터 시작해서, 해당 요소가 가리키고 있는 배열의 요소를 다시 얻어내고, ... 이걸 여러 번 반복해서 배열의 마지막 아이템에 도달할 수 있는지, 있다면 몇 번의 시행만에 도달할 수 있는지 출력하는 문제.

 

주요한 아이디어는 다음과 같다.

- 첫 아이템부터 시작해서 시뮬레이션으로 풀면 된다. 다만 무한히 시행해도 마지막 아이템에 도달하지 못하는 경우가 있을 수 있다.

- n개의 노드로 이루어진 그래프에서는 사이클의 크기가 이무리 커도 n을 넘지 못한다. 그렇기 때문에 시행을 n번 반복했음에도 불구하고 마지막 아이템에 도달하지 못했다면 영영 도달할 수 없다는 말이 된다.

 

a=(0+require('fs').readFileSync(0)).split`
`
x=1
while(a[x]){
  n=+a[x++]
  b=a.slice(x,x+=n)
  i=1
  k=b[0]-1
  while(i<n){if(k==n-1)break;k=b[k]-1;i++}
  console.log(i%n)
}