[구현] 백준 11558 The Game of Death JAVA

[문제출처 |  https://www.acmicpc.net/problem/11558 ]

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

---

처음에 문제를 접하고 아 쉽네~ 했다가 이상한 곳에서 파고들다가 길을 잃었다..

 

처음엔 1차원 배열에 인덱스는 각 사람의 번호라치고, 값은 그 사람이 가리키는 사람의 번호를 담았다.
그리고 while문을 돌며 주경이 번호(N)가 걸릴 때까지 돌면서 주경이를 가리키는 사람의 인덱스를 출력하게 접근했는데..

그래프 탐색인데 인접행렬이나 인접리스트를 쓰는게 낫나?
사이클이 돌면?, 주경이를 가리키는 애가 없거나, 주경이를 가리키는 애가 희현이로부터 연결되어 있지 않다면?

위의 생각들로 class Node를 만들었다가 배열리스트를 썼다가, 연결리스트를 썼다가...
삽질이란 삽질은 다 했다..

이러나 저러나 사이클이 돌 때, 희현이로부터 주경이와 연결되어 있지 않아 무한루프에 빠져버릴 때가 문제였는데
며칠 삽질 좀 하다가 (아니 고작 실버4에 이렇게 골머리 싸맬 일이야~~)

아, 방문 배열을 하나 두자!
온 곳을 또 들리면 사이클을 도는거고, 중간에 연결이 끊어지더라도 희현이와 연결된 라인은 모두 돌면서 방문처리를 했을테니 무한루프 문제도 해결된다.

의외로 간단하게 해결되서 허탈하지만.. 오늘 경험으로 다음엔 더 빨리 생각나겠지 (*✧×✧*)

 

---

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

// 통과 204ms
public class Main_11558 {

	static int N, point[];
	static boolean visited[];

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

		int T = Integer.parseInt(br.readLine());
		for (int i = 0; i < T; i++) {
			N = Integer.parseInt(br.readLine()); // 총 인원
			point = new int[N+1];
			visited = new boolean[N+1]; // 사이클 방지
			
			for (int j = 1; j <= N; j++) {
				point[j] = Integer.parseInt(br.readLine());
			}
			
			int target = 1;
			int cnt = 0;
			while (!visited[target] && target != N) {
				visited[target] = true;
				target = point[target];
				cnt++;
			}
			
			if(target == N) {
				System.out.println(cnt);
			} else {
				System.out.println(0);
			}

		}

	}
}