[python/백준] 17204. 죽음의 게임(S3)

📌 문제 탐색하기

👉 문제바로가기

N: 게임에 참여하는 사람의 수(3 ≤ N ≤ 150)
K: 보성이의 번호(1 ≤ K ≤ N - 1)
ai: i번 사람이 지목하는 사람의 번호(0 ≤ i ≤ N - 1, 0 ≤ ai ≤ N - 1)

지목하는 사람의 번호를 입력받아 차례대로 다음 노드로 이동하여 보성이의 번호(K)를 찾는 문제입니다. 어떤 방법으로도 K를 찾지 못한다면 -1을 출력하면됩니다.

📌 알고리즘 선택

방법1: 단순히 지목하는 번호를 리스트에 담고, 그 번호를 가진 사람이 지목하는 번호를 뽑아 K와 일치하는지 확인하면서 몇 번 불렀는지 카운트하면 됩니다.

방법2: M번만에 보성이에게 도달하는 최단 경로를 찾는 문제이므로 bfs를 활용할 수도 있겠네요.

시간복잡도

1번 방법에서 최악의 경우 시간복잡도는 O(N)입니다. N의 최댓값은 150이므로 O(N)의 시간복잡도를 가진 알고리즘으로도 충분히 시간 내에 연산이 가능합니다.

📌 코드 설계하기

1. N, K를 공백을 두고 Input받습니다.
2. N줄에 걸쳐 각각 사람이 지목하는 사람의 번호를 Input받습니다.
3. 0부터 시작해서 해당 번호의 사람이 지목한 번호의 인덱스로 가서 다음 사람의 번호를 구합니다. 지목할때마다 count를 1씩 증가시키면서 K를 찾으면 count를 출력 후 반복문을 종료시키고, N번만큼 반복하여도 K를 찾지 못하면 종료하고 -1을 출력합니다.

📌 정답 코드

import sys

N, K = map(int, sys.stdin.readline().split())
numbers = [int(sys.stdin.readline()) for _ in range(N)]
count = 0
number = 0

for _ in range(N):
    if number != K:
        number = numbers[number]
        count += 1
    else:
        print(count)
        break
else:
    print(-1)