백준 11558번 The Game of Death(java)

[Silver IV] The Game of Death - 11558

문제 링크

성능 요약

메모리: 19304 KB, 시간: 156 ms

분류

그래프 이론, 그래프 탐색, 구현, 시뮬레이션

제출 일자

2024년 8월 3일 18:57:30

문제 설명

희현이와 주경이는 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을 출력해야 한다.

 

풀이

반복 수열과 비슷한 문제로 끝나지 않는 반복 수열이 나타나면 0을 출력하고

주경이의 위치가 나타나면 지금까지의 반복 횟수를 출력하면 되는 간단한 문제다.

 

그러나 문제가 좀 많이 이상하다.

 

출력 뒤에 무조건 개행을 붙여줘야 테스트 케이스를 통과하며,

 

사람이 한 명일 때는 1을 출력해야 정답으로 인정 된다.

 

희현이가 주경이를 걸리게 하고 싶은 문제인데 한 명이 할 수 있다는게 이해가 안 가며 1이 출력되는 것도 이해가 안 간다.

 

굉장히 별로인 문제다.

전체 코드

public class Main{
    public static void main(String args[])throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        int N  =  Integer.parseInt(br.readLine());

        for(int  i = 0 ;i<N;i++){
            int person = Integer.parseInt(br.readLine());
            
            if(person == 1){
                bw.write("1\n");
                bw.flush();
                continue;
            }
            int x[] = new int[person];
            for(int  j =0 ;j<person;j++){
                x[j] = Integer.parseInt(br.readLine());
            }

            List<Integer> n = new ArrayList<Integer>();
            int k = 0;
            int cnt = 0;
            while(true){
                n.add(k);
                if(n.contains(x[k]-1)){
                    bw.write("0\n");
                    bw.flush();
                    break;
                }

                if(x[k] == person){
                    cnt++;
                    bw.write(String.valueOf(cnt));
                    bw.write("\n");
                    bw.flush();
                    break;
                }
                cnt++;
                k = x[k]-1;
            }
        }
    }
}