[실버 4] The Game of Death

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

11558번: The Game of Death

풀기 전:

N이 10,000

시간제한 1초

딱 1억에 걸리네

 

그냥 while 문 돌면서 N 일 때까지 검사하면 안 되나?

 

import java.io.*;
import java.util.*;

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

        int T;
        int N;
        int[] A;
        int count;
        int start;

        T = Integer.parseInt(br.readLine());
        for (int i = 0; i < T; i++) {
            sb = new StringBuilder();

            N = Integer.parseInt(br.readLine());
            A = new int[N];

            for (int j = 0; j < N; j++)
                A[j] = Integer.parseInt(br.readLine());

            count = 0;
            start = 0;
            while (true) {
                count++;
                start = A[start]-1;

                if (start == N - 1) {
                    sb.append(count);
                    break;
                }
                if (count >= N) {
                    sb.append(0);
                    break;
                }

            }

            System.out.println(sb);

        }
    }
}

돌다가 N-1 이 지목되면 멈추고

N 번 전체 돌았는데도 도달하지 못했다면 영원히 도달하지 못하므로 0출력

 

O(T * N)