[백준] 1103 게임 - DP + 깊이우선탐색(DFS, 재귀) JAVA

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

1103번: 게임

코드설명

DP와 깊이우선탐색(DFS, 재귀)를 활용합니다.

 

DFS를 활용한 이유는 문제에서 맨 마지맊까지 움직이고 계산하도록 지문에 나와있기 때문입니다.

BFS를 활용해도 될 것 같아 보이지만, DFS를 활용했습니다.

 

simulate 함수 설명입니다.

• DFS(깊이 우선 탐색)를 활용하여 모든 가능한 경로를 탐색하고, 각 경로의 이동 횟수를 함수가 실행될떄마다 +1씩 증가시켜 함수의 이동횟수를 확인할 수 있습니다.
• 재귀 호출을 통해 모든 가능한 경로를 탐색하고, 각 위치에서의 최대 이동 횟수를 dp 배열에 저장합니다.
• 만약 이미 해당 위치를 방문한 적이 있다면 사이클이 발생한 것으로 판단하여 2500을 반환합니다.

문제에서 놓쳤었던점은 DP만을 활용하여 최대 이동횟수를 계산하려했지만, 만약 똑같은 위치를 돌아서 다시 해당 위치에 도달한다면 DP로는 알아낼 수 없습니다. 그렇기에 Visited 배열을 활용하여 만약 해당 위치에 다시 들어온다면 바로 사이클로 판별하여 최대값 2500 을 return 해줍니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M, K;
	public static int answer;
	public static int[][] map;
	public static int[] dx = {-1,1,0,0};
	public static int[] dy = {0,0,-1,1};
	public static boolean[][] visited;
	public static int[][] dp;
	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());
    	M = Integer.parseInt(st.nextToken());
    	map = new int[N][M];
    	visited = new boolean[N][M];
    	dp = new int[N][M];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		String str = st.nextToken();
    		for(int j=0;j<M;j++) {
    			map[i][j] = str.charAt(j) - '0';	
    		}
    		
		}
    	
    	visited[0][0] = true;
    	int answer = simulate(new Node(0, 0, 0, 0));
    	if(answer >= 2500) {
    		System.out.println("-1");
    	}else {
    		System.out.println(answer + 1);	
    	}
			
    	
	}
	
	//사이클 판별하는 방법으로 visited를 사용해야하는데. visited[][] , 즉 최대 움직일 수 있는 회수보다 
	public static int simulate(Node start) {
		if(dp[start.r][start.c] != 0) return dp[start.r][start.c]; //dp가 갱신되었다면 이미 해당 공간은 다 탐색되었다는 의미입니다. 하지만 이것으로 싸이클 판별을 할 수 없는 이유는 모두 탐색이 끝나고 재귀로 나오기에 그렇습니다.
		int result = 0;
		Node temp = start;
		for(int dir = 0; dir < 4; dir++) {
			int nr = temp.r + dx[dir] * map[temp.r][temp.c];
			int nc = temp.c + dy[dir] * map[temp.r][temp.c];
			
			if(nr < 0 || nr >= N || nc < 0 || nc >= M) {
				continue;
			}
			if(map[nr][nc] == 'H' - '0') {
				continue;
			}
			if(visited[nr][nc] == true) {
				return 2500;
			}
			visited[nr][nc] = true;
			result = Math.max(result, simulate(new Node(nr, nc, dir, temp.cnt + 1)) + 1);
			visited[nr][nc] = false;
		}
		
		return dp[start.r][start.c] = result;
	}
 
	
}
class Node{
	int r;
	int c;
	int dir;
	int cnt;
	public Node(int r, int c, int dir, int cnt) {
		this.r=r;
		this.c = c;
		this.dir = dir;
		this.cnt = cnt;
	}
}