[Baekjoon 11558] The Game of Death - JAVA

[Silver IV] The Game of Death - 11558

문제 링크

성능 요약

메모리: 18412 KB, 시간: 176 ms

분류

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

문제 설명

희현이와 주경이는 The Game of Death를 좋아한다.

The Game of Death 규칙:

1. 플레이어는 각자 한 명씩 지목을 한다(자신도 가능).
2. 처음 시작하는 사람은 임의의 자연수 K를 말한다.
3. 시작한 사람부터 지목한 사람을 차례대로 따라가다가 K번째 지목당한 사람이 걸리게 된다.

희현이는 희현이부터 이 게임을 시작할 때 이 게임에서 반드시 주경이를 반드시! 걸리게 하고 싶다. 주경이가 걸릴 수 있도록 희현이를 도와주자.

입력

첫 줄에는 테스트 케이스의 숫자 T가 주어지며, 이어서 T번에 걸쳐 테스트 케이스들이 주어진다.

매 테스트 케이스의 첫 줄에는 플레이어의 숫자 N(1 ≤ N ≤ 10,000)이 주어진다.

이어서 N줄에 걸쳐 각 플레이어가 지명한 사람의 숫자 A_i(1 ≤ A_i ≤ N, 1 ≤ i ≤ N)이 주어진다.

희현이는 1번, 주경이는 N번이다,

출력

매 테스트 케이스마다 한 줄에 걸쳐 희현이가 주경이를 걸리게 하고 싶을 때 불러야 하는 최소 숫자 K를 출력한다.

만약 어떤 숫자를 말해도 주경이가 걸리지 않는다면 0을 출력해야 한다.

문제 풀이

해당 문제는 순열의 사이클을 찾으면 쉽게 풀 수 있다.

예를 들자면 아래와 같다.

입력:

2       // 테스트 케이스 개수
6       // 첫 번째 테스트 케이스에서의 N 값
3       // 1번 인덱스에 해당하는 숫자
1       // 2번 인덱스에 해당하는 숫자
6       // 3번 인덱스에 해당하는 숫자
4       // 4번 인덱스에 해당하는 숫자
2       // 5번 인덱스에 해당하는 숫자
5       // 6번 인덱스에 해당하는 숫자
4       // 두 번째 테스트 케이스에서의 N 값
2       // 1번 인덱스에 해당하는 숫자
3       // 2번 인덱스에 해당하는 숫자
1       // 3번 인덱스에 해당하는 숫자
4       // 4번 인덱스에 해당하는 숫자

출력:

2
0

위 입력을 통해 사이클을 찾아내면 아래와 같다.

첫 번째 케이스의 경우

1 -> 3 -> 6 -> 5 -> 2 -> 1

여기서 주경이는 N 즉 6이기 때문에 희현이가 최소 숫자인 2를 출력하면 된다.

두 번째 케이스의 경우

2 -> 3 -> 1 -> 4

여기서 1, 2, 3은 서로 사이클로 연결되어 있으나 4는 떨어져 있다. 때문에 주경이는 걸리지 않기 때문에 0을 출력하면 된다.

위 알고리즘을 구현하면 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

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

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

        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());

            int[] arrSelect = new int[n + 1];
            boolean[] visited = new boolean[n + 1];

            for (int i = 1; i <= n; ++i) {
                arrSelect[i] = Integer.parseInt(br.readLine());
            }

            int number = arrSelect[1];
            int count = 1;
            visited[1] = true;

            while (true) {
                if (number == n) {
                    break;
                }
                if (visited[arrSelect[number]]) {
                    break;
                }
                ++count;
                number = arrSelect[number];
                visited[number] = true;
            }

            if (number == n) {
                sb.append(count).append("\n");
            } else {
                sb.append("0\n");
            }
        }

        System.out.print(sb);
    }
}

코드 풀이

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

• 변수 t에 정수를 입력받는다.

while (t-- > 0) {

• 테스트 케이스의 개수만큼 반복문을 실행한다. 0이 되기 전까지 반복한다.

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

int[] arrSelect = new int[n + 1];
boolean[] visited = new boolean[n + 1];

for (int i = 1; i <= n; ++i) {
arrSelect[i] = Integer.parseInt(br.readLine());
}

- 테스트 케이스마다 배열과 방문 여부를 초기화한다.
- `n` 변수에는 배열의 크기를 입력받고, `arrSelect` 배열에는 입력받은 크기만큼의 값을 순서대로 저장하고 있다.

int number = arrSelect[1];
int count = 1;
visited[1] = true;

while (true) {
if (number == n) {
break;
}
if (visited[arrSelect[number]]) {
break;
}
++count;
number = arrSelect[number];
visited[number] = true;
}

- 주어진 규칙에 따라 배열에서 숫자를 탐색하고 카운트하는 과정을 수행한다.
- `number` 변수에는 시작 숫자를 저장하고, `count` 변수에는 탐색하는 숫자의 개수를 카운트하고 있다.
- `visited` 배열은 방문한 숫자를 표시하기 위해 사용되고, 이미 방문한 숫자를 만나면 탐색을 종료한다.

if (number == n) {
sb.append(count).append("\n");
} else {
sb.append("0\n");
}

- 탐색이 끝났을 때 결과를 `StringBuilder`에 누적한다.
- number`가 `n`과 같다면 숫자 탐색이 끝났으므로 `count`를 `StringBuilder`에 추가하고, 그렇지 않다면 0을 추가한다.

System.out.print(sb);

```

• StringBuilder에 누적된 결과를 출력합니다.