[백준] 17204번: 죽음의 게임 (Java)

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

📌 문제 탐색하기

입력 : 첫째 줄 - 게임에 참여하는 사람의 수 N, 보성이의 번호 K (3 ≤ N ≤ 150, 1 ≤ K ≤ N - 1)
N줄 - i번 사람이 지목하는 사람의 번호 ai(0 ≤ i ≤ N - 1, 0 ≤ ai ≤ N - 1)
출력 : 영기가 말해야 하는 가장 작은 양의 정수 M
단, 어떤 방법으로도 보성이가 걸리지 않으면 -1 출력

가능한 시간복잡도

O(N)

알고리즘 선택

그래프 탐색

📌 코드 설계하기

1. 학생 수 N과 목표 학생의 번호 K를 입력받는다.
2. 각 학생이 가리키는 학생의 번호를 저장할 배열 students를 선언하고 입력받는다.
3. 각 학생의 방문 여부를 체크할 배열 visited를 선언한다.
4. 시작 학생을 0번 학생으로 설정하고 현재 위치를 current 변수에 저장한다.
5. 방문하지 않은 학생을 따라가면서 목표 학생 K에 도달하면 걸린 단계를 출력하고 종료한다.
6. 만약 방문한 학생을 다시 방문하게 되면(사이클 발생), 목표 학생에게 도달할 수 없으므로 -1을 출력한다.

📌 시도 회차 수정 사항 (Optional)

💡 시도별 수정 사항은 어떻게 작성하나요?
- 무문별하게 “맞았습니다”가 나올때 까지 수정하는 형태의 문제 풀이를 반복하면 , 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 됩니다.
- 틀렸습니다를 받았다면 왜 틀렸는지 고민해보고 , 어떻게 수정할 수 있는지 고민하는 과정을 작성해주시면 됩니다.
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검해보세요
- 한번에 맞출수도 있기 때문에 이 칸은 Optional입니다.

1회차

2회차

📌 정답 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt(); // 학생 수
        int K = sc.nextInt(); // 목표하는 학생의 번호
        
        int[] students = new int[N]; // 각 학생이 가리키는 학생을 저장하는 배열
        
        for (int i = 0; i < N; i++) {
            students[i] = sc.nextInt(); // i번 학생이 가리키는 학생의 번호 입력
        }
        
        boolean[] visited = new boolean[N]; // 방문 체크 배열
        int current = 0; // 시작 학생은 0번 학생
        int steps = 0; // 걸린 단계 수
        
        while (!visited[current]) {
            if (current == K) {
                System.out.println(steps);
                return;
            }
            visited[current] = true;
            current = students[current];
            steps++;
        }
        
        System.out.println(-1); // 목표 학생에게 도달할 수 없을 경우 -1 출력
    }
}