[백준] 11558번 The Game of Death (Python)

Posted: 2024.11.12     Updated: 2024.11.12

문제

풀이

알고리즘 분류가 구현, 그래프 이론, 그래프 탐색, 시뮬레이션이다.
대다수의 사람들이 DFS를 활용하여 해결하는 것 같았으나, 그래프 탐색을 사용하지 않고 해결했다.

실제 The Game of Death 게임을 생각하면 숫자를 아무리 크게 불러도 시작한 사람을 포함한 특정 몇 명만 계속 반복하여 따라가게 된다.
그럼 사이클이 생기게 되고 참여자 수가 N명이라면 사이클 내에 포함될 수 있는 최대 인원은 N명이다.
따라서 희현이부터 시작해 가리킨 사람을 N번 반복하여 따라갔을 때, 주경이가 등장하기 까지의 횟수가 최소 숫자 K이고, N번 반복이 끝나도 주경이가 나오지 않는다면 0을 출력하면 된다.

소스코드

T = int(input())

for _ in range(T):
    N = int(input())
    li = [int(input()) for _ in range(N)]
    n = 0
    r = 0
    b = False

    for _ in range(N):
        if n != N - 1:
            n = li[n] - 1
            r += 1
        else:
            b = True
            break

    print(r if b else 0)