백준 17204번 죽음의 게임 (JAVA)

백준 17204번 죽음의 게임 (JAVA)

문제

난이도

• 실버 3

알고리즘 분류

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

풀이

출발번호(0) 부터 목표번호(K)로 가는 최솟값 구하기

어떤 방법으로도 K로 갈 수 없는 경우는 K에 도착하기 전에 사이클이 발생한다.

코드

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(in.readLine());

        int N = Integer.parseInt(st.nextToken());   // 참가자 수
        int K = Integer.parseInt(st.nextToken());   // 보성이 번호

        int target[] = new int[N];

        for (int i = 0; i < N; i++) {
            target[i] = Integer.parseInt(in.readLine());
        }

        Set<Integer> game = new HashSet<Integer>(); // 중복을 피하기 위한 자료구조 Set 사용

        int size = 0;                               // Set의 크기
        int answer = -1;                            // 정답
        int start = 0;                              // 시작은 항상 0
        int cnt = 0;                                // 게임이 진행되는 횟수

        while(true) {
            size = game.size();                     // Set의 크기 구하기
            cnt++;                                  // 게임 1회 진행
            int next = target[start];               // 현재 사람이 지목한 다음 사람
            if(next == K) {                         // 다음 사람이 K인 경우
                answer = cnt;                       // 정답은 현재까지 진행한 횟수
                break;                              // 반복 종료
            }

            start = next;                           // 다음 게임의 시작은 현재 사람이 지목한 사람
            game.add(next);                         // 지목한 사람을 Set에 추가

            if(size == game.size()) {               // Set의 크기 변화가 없는 경우, 한 번 지목당한 사람이 다시 지명되었다. 즉, 사이클이 발생한다.
                break;                              // 반복 종료, 도달할 수 없기 때문에 정답은 -1
            }
        }

        sb.append(answer);
        out.write(sb.toString());
        out.close();
    }
}