[JAVA] 백준 17204_죽음의 게임

 

[문제링크]

https://www.acmicpc.net/problem/17204

 

 

📌 문제 탐색하기

 

• N명의 사람들이 원탁에 앉아 있으며, 각 사람은 특정 다른 사람을 지목한다.
• 0번 사람이 시작하며 "1"부터 MMM까지 숫자를 외칩니다.
• MMM번째로 숫자를 외친 사람이 지목한 대상이 벌주를 마십니다.

이때, 보성이(KKK)가 벌주를 마시도록 하기 위해, 0번 사람이 불러야 하는 가장 작은 MMM을 찾습니다.

보성이 벌주를 마실 수 없는 경우에는 −1-1−1을 출력

 

 

📌 가능한 시간복잡도 

각 노드는 최대 한 번만 방문하기 때문에 가능한 시간복잡도는 O(N) 이라고 생각함.

 

📌 코드 설계하기

1. N과 K의 값을 입력받는다.

2. 각각 지목된 정보를 배열에 저장하기

3. BFS 탐색을 활용하기

 

📌 정답 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        int N = in.nextInt(); 
        int K = in.nextInt(); 
        
        int[] targets = new int[N];
        for (int i = 0; i < N; i++) {
            targets[i] = in.nextInt();
        }
        
        System.out.println(findMinimumM(N, K, targets));
    }
    
    public static int findMinimumM(int N, int K, int[] targets) {
        boolean[] visited = new boolean[N]; 
        int current = 0; 
        int steps = 0; 
        
       
        while (!visited[current]) {
            visited[current] = true; 
            steps++;
            
            if (targets[current] == K) {
                return steps;
            }
            
          
            current = targets[current];
        }
        
        return -1;
    }
}