17204 죽음의 게임 (python)

17204 죽음의 게임

 

문제 🌐

중앙대학교 소프트웨어대학 새내기들을 맞이하게 된 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을 출력한다.

접근 방법

list에는 각자가 자기 차례가 오면 누구를 지목할지 마음속으로 정해 두고 있다. 만약 이들이 차근차근 연결돼서 보성이가 걸리면 성공! 이건 마치 사랑의 작대기 혹은 러시안 룰렛….

예시 1

입력

5 3
1 3 2 1 4

출력

2

소프트웨어학과의 절망적인 성비를 표현해 보았다. 노랑색은 자폭 한 경우를 말한다. 여기서는 단 2번의 시도로 보성이를 보내 버릴 수 있다. 1번과 보성이가 서로를 지목하고 있기 때문에 짝수만 부른다면 얼마든지 가능하다.

예시 2

입력

6 2
1 3 5 4 0 2

출력

-1 

이 경우에는 안타깝게도 보성이를 보내 버릴 수 없다. 영기의 화살표를 따라가 보면 보성이에게 닿을 수 없는 상태이다…. 여기서는 오히려 영기가 마실 위험이 있다. 이걸 어떻게 코드로 만들어낼 것인가?…

리스트와 인덱스를 이용해서 리스트 값을 인덱스에 계속 집어넣어 탐색하는 방식으로 했다. 어쨌든 한 바퀴를 돌면서 누가 누구를 지목했는지 확인하면 끝날 것이라 생각했다.

point가 지목하는 사람이 되고, sequence[point] 가 point의 타겟이 된다. 반복문의 경우가 넘어갈 때마다 point에 sequence[point]를 넣어주는 방식으로 매번 주인공을 넘기는 방식이고, 답에 보성이의 번호가 나오면 반복문을 빠져나온다. 그래도 나오지 않는다면 실패한 것으로, -1 프린트 한다.

Full Solution

N, K = map(int, input().split())
sequence = []

# 리스트에 지목 순서 넣기
for i in range(N):
    sequence.append(int(input()))

# 처음 지목하는 사람은 게임을 제안한 0번
point = 0
# 카운트
cnt = 0

for _ in range(N):
    point = sequence[point]
    cnt += 1
    if point == K:
        print(cnt)
        break
else:
    print(-1)