[백준] 17204 죽음의 게임 - DFS(깊이우선탐색) JAVA

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

코드설명

DFS(깊이우선탐색)을 활용해야 합니다.

 

문제에 대한 이해가 중요한 문제입니다. 

"이때 마지막으로 M이라고 말한 사람이 지목한 사람은 벌주를 마시게 된다."라는 문구를 주의합니다.

 

문제에 대한 주의사항입니다.

1. nowIdx는 현재 사람의 인덱스로써, 우리는 m이 1 인경우도 고려해야 하므로 아래와 같이 실행합니다.

처음에 find(arr[0], K, 0, m) 으로 처리했었는데 

0번쨰 사람이 1번이라고 외치면서 만약, m번이 1이라면, 그 0번쨰 사람이 외친 사람이 벌주를 마셔야합니다.

for(int m=1; m<=N; m++) {
    if( find(0, K, 1, m) == true ) {
        answer = m;
        break;
    }
}

이떄, M번이라고 말한사람이 지목한 사람이 벌주를 마시는 것이므로, 0번쨰 사람이 외친사람도 고려하기 위해 

find(0, K, 1, m) 으로 실행한다는 점을 유의합니다.

 

코드

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, M, C, T, K;
    private static int answer = 0;
    private static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        arr = new int[N];
        for(int i=0;i<N;i++) {
        	st = new StringTokenizer(br.readLine());
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        answer = -1;
        for(int m=1; m<=N; m++) {
        	if( find(0, K, 1, m) == true ) {
        		answer = m;
        		break;
        	}
        }
        
        System.out.println(answer);
        
    }
    
    public static boolean find(int nowIdx, int target, int cnt, int targetM) {
    	if( cnt == targetM) {
    		if(arr[nowIdx] == target) return true;
    		else return false;
    	}
    	
//    	System.out.println("now:"+now);
    	return find(arr[nowIdx], target, cnt + 1, targetM);
    }
    
}