[백준] 17204번 : 죽음의 게임 자바(JAVA) 풀이

문제

---

---

문제 탐색하기

 

한 사람이 지목한 다음 사람을 구하는 탐색 과정을 거쳐서 이 과정에서

한 사람 → 다음 사람으로 한 간선을 넘어가는 개수를 체크한다.

 

경우의 수

1. 보성이가 걸리는 경우
   • 만나는 노드가 보성이가 될 때 탐색 종료
2. 보성이가 걸릴 수 없는 경우
   • 한 번 탐색을 다 돌았는데 보성이를 거치지 않는 경우 -1 출력
3. 두 경우가 아닌 경우
   • 연결된 다음 노드 탐색

 

가능한 시간복잡도

입력 범위 ( 3 ≤ N ≤ 150)

K를 만나지 못할 경우에도 최대 정점의 개수만큼만 탐색하기 때문에

시간 복잡도는 O(N) 이 된다.

 

---

코드 설계하기

• 입력받는 값을 그래프로 생각하고 배열에 저장한다.
• While 문을 통해서 0번부터 탐색을 진행한다.
  • 보성이가 걸리면 break;
  • 보성이가 걸리지 않는 경우 -1 출력 후 break;
  • 두 경우가 아니라면 탐색을 계속한다.

---

풀이 코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 게임에 참여하는 사람의 수
		int K = Integer.parseInt(st.nextToken()); // 보성이의 번호
		
		int[] graph = new int[N]; // 사람이 지목하는 사람의 번호
		for(int i=0;i<N;i++) {
			graph[i] = Integer.parseInt(br.readLine());
		}
		
		int start = 0; // 0 번 부터 시작
		int count = 0; // 보성이가 걸릴 가장 작은 수
		while(true) {
			if(start == K) { // 보성이가 걸리는 경우
				break;
			} else if (count > N) { // 보성이가 걸리지 않는 경우
				count = -1;
				break;
			} else { // 연결된 다음 노드 탐색
				start = graph[start];
				count++;
			}
		}
		System.out.println(count);
	}
}