<코테 챌린지> 죽음의 게임 (백준 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을 출력한다.

📥 예제 입력

5 3
1
3
2
1
4

📤 예제 출력

2

 

👩🏻‍💻 내 코드

 

package baekjoon.코테챌린지;

import java.util.Scanner;

public class 죽음의게임 {
    /**
     * 영기는 보성이에게 벌주를 먹이고 싶어한다.
     * 영기부터 시작해서 M번 동안 다른 사람들이 순서대로 번호를 부르고,
     * 마지막 M번을 부른 사람이 보성이를 지목하게 되어야 하는 문제
     *
     * 즉 영기(0번)로부터 시작해서 보성이(K번)가 지목될 때까지 가장 작은 정수 M을 찾는 것이 핵심
     * **/
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt(); // 참여하는 사람 수
        int K = in.nextInt(); // 보성이 번호 (지게 해야하는 친구)

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = in.nextInt();
        }

        int num = 0;
        int count = 0;
        boolean[] visited = new boolean[N];

        while (true) {

            if(visited[num]) {
                System.out.println(-1);
                break;
            }
            visited[num] = true;  // 현재 사람을 방문으로 표시

            if(num == K) {
                System.out.println(count);
                break;
            }

            num = arr[num];
            count++;

        }

    }

}

 

💡 코드 접근

 

처음에는 문제가 이해 가다가도 헷갈리고... 그랬다 …

 

차근차근 문제에서 말하는 ‘죽음의 게임’의 핵심부터 파악해보자

문제에서 영기는 보성이에게 벌주를 먹이고 싶어한다. 영기부터 시작해서 M번 동안 다른 사람들이 순서대로 번호를 부르고, 마지막 M번을 부른 사람이 보성이를 지목하게 되어야 하는 문제이다!

즉 영기(0번)로부터 시작해서 보성이(K번)가 지목될 때까지 가장 작은 정수 M을 찾는 것이 핵심이다

5 3
1
3
2
1
4

 

두번째 줄부터는 본인이 지목한 사람의 번호를 나타내고 있는데, i번째 줄에 있는 숫자는 i번 사람이 누구를 지목했는지를 나타내는 것이다.

• 0번은 1번을 지목.
• 1번은 3번을 지목.
• 2번은 2번을 지목.
• 3번은 1번을 지목.
• 4번은 4번을 지목.

위 예제에서는 영기(0번)가 1번을 지목하고, 1번은 3번을 지목한다.

 0 → 1 → 3의 경로를 통해 보성이(3번)가 걸리게 되며 2번에 의해 보성이가 불렸기에 M = 2가 답이 된다.

 

즉 영기(0번)부터 시작해서 계속 지목된 사람으로 이동하는 코드를 짜야한다.

• 현재 호출된 사람에 방문 표시를 하고, 만약 보성이에게 도달하지 못하고 계속 방문한 사람을 또 방문하게 되면 -1을 출력하여 종료한다.
• 처음에 num에는 0이 들어오므로 num = arr[num] 이후에 num에 들어갈 숫자는 0번이 부른 사람일 것이다. 그럼 이후 지목된 사람이 num이 되고, 그 사람이 지목하는 사람으로 이동 .. 이런식으로 호출된다.
  • 호출할 때마다 count를 올려준다.
• 보성이(K번)에게 도달하면 그때까지의 카운트를 출력해준다.

int num = 0;
int count = 0;
boolean[] visited = new boolean[N];

while (true) {

    if(visited[num]) {
        System.out.println(-1);
        break;
    }
    visited[num] = true;  // 현재 사람을 방문으로 표시

    if(num == K) {
        System.out.println(count);
        break;
    }

    num = arr[num];
    count++;

}