[백준] 17090 미로 탈출하기 - DFS(깊이우선탐색) + DP(Dynamic Programming) JAVA

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

17090번: 미로 탈출하기

코드설명

DFS(깊이우선탐색) + DP(Dynamic Programming)를 활용하는 문제입니다.

 

처음에는 DP를 활용하지 않아 시간초과가 납니다.

미리 해당 칸이 성공한 칸인지, 실패한칸인지를 순회하면서 모두 저장해야하는 문제입니다.

 

visited, successDP를 전역적으로 사용하여

visited는 이미 방문한 여부를 확인합니다.

successDP는 성공여부를 저장합니다.

 

만약 visited는 true이면서 successDP가 false라면 해당 칸은 실패한 칸이라고 생각하면 됩니다.

successDP가 true라면 해당 칸은 밖으로 나갈 수 있는 칸입니다.

 

public static boolean DFS(int level, int r, int c) {
    visited[r][c] = true;
    int nr = r + dx[map[r][c]];
    int nc = c + dy[map[r][c]];

    if( nr <= 0 || nr >= N+1 || nc <= 0 || nc >= M+1 || successDP[nr][nc] == true) {
        successDP[r][c] = true;
        return true;
    }

    if(visited[nr][nc] == true && successDP[nr][nc] == false) return false;
    return successDP[r][c] = DFS(level + 1, nr, nc);
}

1. 먼저 시작칸을 방문하였으니 먼저 visited[r][c] = true로 선언합니다.

2. 다음칸이 만약 밖으로 나간다면 successDP는 해당 칸을 성공칸으로 둡니다. 

3. 다음칸이 혹은 이미 sucessDP[nr][nc] = true로써 밖으로 나가는 칸이라면 성공 칸으로 두고 return true합니다.

4. 만약 이미 visited[nr][nc] == true이고, successDP가 false라면 해당 칸은 밖으로 나가지 못하는 칸이니 false를 return 합니다.

5. successDP값이 성공여부를 저장하며 밖으로 나옵니다.

 

그리고 마지막으로는 successDP가 true인칸을 모두 세어서 나가는 칸이 몇개인지 셉니다.

 

혹은 successDP를 활용하지 않고, Map칸에 애초에 'Success', 'Fail' 여부의 문자 'S', 'F'를 저장하여 진행하면 메모리 공간은 더 적게 사용할 수 있습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M;
	public static long answer = 0;
	public static int[] arr;
	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 boolean[][] successDP;
	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 + 2][M + 2];
    	visited = new boolean[N + 2][M+2];
    	successDP= new boolean[N + 2][M+2];
    	for(int i=1;i<=N;i++) {
    		st = new StringTokenizer(br.readLine());
    		String input = st.nextToken();
    		for(int j=1;j<=M;j++) {
    			if( input.charAt(j - 1) == 'U' ) {
    				map[i][j] =  0;
    			}
    			else if( input.charAt(j - 1) == 'D' ) {
    				map[i][j] =  1;
    			}
    			else if( input.charAt(j - 1) == 'L' ) {
    				map[i][j] =  2;
    			}
    			else if( input.charAt(j - 1) == 'R' ) {
    				map[i][j] =  3;
    			}
    		}
    	}
    	
    	for(int i=1;i<=N;i++) {
    		for(int j=1;j<=M;j++) {
    			DFS(0, i, j);
    		}
    	}
    	
    	for(int i=1; i<=N;i++) {
    		for(int j=1; j<=M;j++) {
    			if(successDP[i][j] == true) {
    				answer += 1;
    			}
    		}
    	}
    	
    	
    	System.out.println(answer);
	}
	
	public static boolean DFS(int level, int r, int c) {
		visited[r][c] = true;
		int nr = r + dx[map[r][c]];
		int nc = c + dy[map[r][c]];
		
		if( nr <= 0 || nr >= N+1 || nc <= 0 || nc >= M+1 || successDP[nr][nc] == true) {
			successDP[r][c] = true;
			return true;
		}
		
		if(visited[nr][nc] == true && successDP[nr][nc] == false) return false;
		return successDP[r][c] = DFS(level + 1, nr, nc);
	}
	
}

 

시간초과 나는 코드입니다..

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M;
	public static long answer = 0;
	public static int[] arr;
	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 boolean[][] cycleCheck;
	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 + 2][M + 2];
    	visited = new boolean[N + 2][M+2];
    	cycleCheck = new boolean[N + 2][M+2];
    	for(int i=1;i<=N;i++) {
    		st = new StringTokenizer(br.readLine());
    		String input = st.nextToken();
    		for(int j=1;j<=M;j++) {
    			map[i][j] = input.charAt(j - 1) - 'A';
    		}
    	}
    	
    	for(int i=1;i<=N;i++) {
    		for(int j=1;j<=M;j++) {
    			if(cycleCheck[i][j] == true) continue; //만약 이미 싸이클이 판별되었다면,
    			
    			if(visited[i][j] == true) {
    				answer += 1;
    				continue;
    			}
    			else if(visited[i][j] == false) {
    				if( DFS(0, i, j) == true) {
    					visited[i][j] = true;
    					answer += 1;
    				}
    			}
    		}
    	}
    	
    	
    	System.out.println(answer);
	}
	
	public static boolean DFS(int level, int r, int c) {
		if(r == 0 || r == N + 1 || c == 0 || c == M + 1) return true;
		if(level == N * M || visited[r][c] == true || cycleCheck[r][c] == true) {
			cycleCheck[r][c] = true;
			return false;
		}
		
		int nr = 0;
		int nc = 0;
		if( map[r][c] == ('D' - 'A')) {
			nr = r + 1;
			nc = c;
		}
		else if(map[r][c] == ('L' - 'A')) {
			nr = r;
			nc = c - 1;
		}
		else if(map[r][c] == ('U' - 'A')) {
			nr = r - 1;
			nc = c;
		}
		else if(map[r][c] == ('R' - 'A')) {
			nr = r;
			nc = c + 1;
		}
		//만약 해당 칸이 나간경우라면, visited 칸을 true로 바꾸면서 나온다. 
		if( DFS(level + 1, nr, nc) == true) {
			visited[r][c] = true;
			return true;
		}
		
		cycleCheck[r][c] = true;
		return false;
	}
	
}