[BOJ | Python] 11558번: The Game of Death

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

 

 

문제

희현이와 주경이는 The Game of Death를 좋아한다.

The Game of Death 규칙:

1. 플레이어는 각자 한 명씩 지목을 한다(자신도 가능).
2. 처음 시작하는 사람은 임의의 자연수 K를 말한다.
3. 시작한 사람부터 지목한 사람을 차례대로 따라가다가 K번째 지목당한 사람이 걸리게 된다.

희현이는 희현이부터 이 게임을 시작할 때 이 게임에서 반드시 주경이를 반드시! 걸리게 하고 싶다. 주경이가 걸릴 수 있도록 희현이를 도와주자.

 

 

입력

첫 줄에는 테스트 케이스의 숫자 T가 주어지며, 이어서 T번에 걸쳐 테스트 케이스들이 주어진다.

매 테스트 케이스의 첫 줄에는 플레이어의 숫자 N(1 ≤ N ≤ 10,000)이 주어진다.

이어서 N줄에 걸쳐 각 플레이어가 지명한 사람의 숫자 Ai(1 ≤ Ai ≤ N, 1 ≤ i ≤ N)이 주어진다.

희현이는 1번, 주경이는 N번이다,

 

 

출력

매 테스트 케이스마다 한 줄에 걸쳐 희현이가 주경이를 걸리게 하고 싶을 때 불러야 하는 최소 숫자 K를 출력한다.

만약 어떤 숫자를 말해도 주경이가 걸리지 않는다면 0을 출력해야 한다.

 

 

풀이

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N = int(input())
    A = [0] + [int(input()) for _ in range(N)]  # 1-based 인덱스
    visited = [False] * (N + 1)

    cur = 1
    cnt = 0

    while not visited[cur]:
        visited[cur] = True
        cnt += 1
        if A[cur] == N:
            print(cnt)
            break
        cur = A[cur]
    else:
        # while이 중간에 break 없이 종료 → 사이클만 돌고 N에 못 감
        print(0)