[백준] 23741번 야바위 게임 자바

문제

 

23741번: 야바위 게임

 

 

문제 풀이

 

dfs+dp 문제. 처음에 dfs로만 했다가 시간초과떴다.

dfs로는 시작 정점에서 움직인 횟수를 카운트하면서 모든 경우에 대해 도착 지점을 확인한다.

dp로는 해당 지점과 같은 카운트를 가지고 온 경우는 처리하지 않도록 표시해둔다.

 

DP[i][j] = i노드의 j번의 횟수로 가는 모든 경우를 처리 했는가? → true 

DFS에서는 해당 노드와 카운트를 가지고 다시 DFS를 수행할지 결정한다.

 

소스 코드

 

public class Main {
	static ArrayList<Integer>[] g;
	static boolean[][] dp;
	static int[] answer;
	static int Y, idx = 0;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] str = br.readLine().split(" ");
		int N = Integer.parseInt(str[0]);	//정점개수
		int M =  Integer.parseInt(str[1]);	//간선 수
		int X =  Integer.parseInt(str[2]);	//공 처음정점
		Y =  Integer.parseInt(str[3]);		//공 움직임 횟수
		
		g = new ArrayList[N+1];
		for(int i = 1; i < N+1; i++)
			g[i] = new ArrayList<Integer>();

		dp = new boolean[N+1][Y+1];
		answer = new int[N+1];
		
		for(int i = 0; i < M; i++) {
			str = br.readLine().split(" ");
			int a = Integer.parseInt(str[0]);
			int b = Integer.parseInt(str[1]);
			g[a].add(b);
			g[b].add(a);
		}
		
		dfs(X, 0);
		
		if(answer[0] == 0)
			System.out.println("-1");
		else {
			Arrays.sort(answer, 0, idx);
			for(int i = 0; i < idx; i++)
				System.out.print(answer[i] + " ");
		}
		
	}

	public static void dfs(int node, int total) {
		
		dp[node][total] = true;	//현재 이 노드에서 total개수를 가지고 갈 수 있는 경우는 다 봤다
		
		if(total == Y) {
			answer[idx++] = node;
			return;
		}
		
		for(int i = 0; i < g[node].size(); i++) { //시작 노드에 연결된 개수만큼 돌면서
			int nextNode = g[node].get(i);	//연결된 다른 노드
			
			if(!dp[nextNode][total+1])
				dfs(nextNode, total+1);
		}

		return;
	}

}