[백준] 17090. 미로 탈출하기(골드3) - DFS

17090. 미로 탈출하기 (골드3)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	6062	2105	1529	33.738%

문제

크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다.

어떤 칸(r, c)에 적힌 문자가

U인 경우에는 (r-1, c)로 이동해야 한다.
R인 경우에는 (r, c+1)로 이동해야 한다.
D인 경우에는 (r+1, c)로 이동해야 한다.
L인 경우에는 (r, c-1)로 이동해야 한다.
미로에서 탈출 가능한 칸의 수를 계산해보자. 탈출 가능한 칸이란, 그 칸에서 이동을 시작해서 칸에 적힌대로 이동했을 때, 미로의 경계 밖으로 이동하게 되는 칸을 의미한다.

입력

첫째 줄에 미로의 크기 N, M(3 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개의 줄에는 미로의 각 칸에 적힌 문자가 주어진다.

출력

첫째 줄에 탈출 가능한 칸의 수를 출력한다.

예제 입력 1
3 3
DDD
DDD
DDD

예제 출력 1
9

예제 입력 2
3 3
RRD
RDD
ULL

예제 출력 2
0

풀이

1. 하나씩 배열 돌면서 검사 => DFS로 밑으로 내려가기
2. 범위 벗어나면 탈출 성공 true
   2.1. 기억배열에서 T면 전에 탈출 가능했던 위치여서 DFS 더 내려가지 않고 바로 탈출 성공을 파악할 수 있다
   2.2. 기억배열에서 F면 전에 탈출 불가능했던 위치여서 DFS 더 내려가지 않고 바로 탈출 실패를 파악할 수 있다
   2.3. 방문했던 곳인데 기억 배열에 T,F 적용안되어 있으면 false
3. 위에 조건 다 통과하고 새로 방문한 곳이면 방문체크
4. 조건에 맞는 DFS 내려가기
5. 기억배열에 탈출 실패여부 정리
6. 탈출 여부 리턴

public class Search_17090 {
	public static int N, M;
	public static String[][] map; // 기억배열 
	public static int[][]  visited; // 방문배열

	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 String[N][M];
		visited = new int[N][M];
		
		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			String[] strArr = str.split("");
			for(int j = 0; j < M; j++) {
				map[i][j] = strArr[j];
			}
		}
		
		int count = 0; //시도 횟수
		for (int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				if(DFS(i,j)) count++;
			}
		}
		
		System.out.println(count);
	}
	
	 public static boolean DFS(int x, int y) {
/*					                          
        // 각 DFS에서 위치에 대한 memorization 배열과 방문 배열 확인	     
 	    System.out.println(x+","+y+"==============================================");
        System.out.println(x+"----------------------------------"+y);
		for (int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				System.out.print(map[i][j]);
			}
			System.out.println();
		}
		System.out.println(x+"----------------------------------"+y);
			for (int i = 0; i < N; i++) {
				for(int j = 0; j < M; j++) {
					System.out.print(visited[i][j]);
				}
				System.out.println();
			}
	    System.out.println("==============================================");
*/
		
		boolean result = false; // 처음에는 false로 초기화
		
        if (x<0 || y<0 || x>=N || y>=M ) return true; // 범위 넘어가면 탈출 성공
        // 기억배열에서 T면 전에 탈출 가능했던 위치여서 DFS 더 내려가지 않고 바로 탈출 성공을 파악할 수 있다
        if (map[x][y].equals("T")) return true; 
         // 기억배열에서 F면 전에 탈출 불가능했던 위치여서 DFS 더 내려가지 않고 바로 탈출 실패를 파악할 수 있다
        else if (map[x][y].equals("F")) return false;
        
        // 방문했던 곳인데 기억 배열에 T,F 적용안되어 있으면 false 
        if (visited[x][y]==1) return false;
        
        // 위에 조건 다 통과하고 새로 방문한 곳이면 방문체크
        visited[x][y] = 1;
        
        // 조건에 맞는 DFS 내려가기
        if (map[x][y].equals("U")) result = DFS(x-1,y);
        else if (map[x][y].equals("R")) result = DFS(x,y+1);
        else if (map[x][y].equals("L")) result = DFS(x,y-1);
        else if (map[x][y].equals("D")) result = DFS(x+1,y);
		
        // 기억배열에 탈출 실패여부 정리
        map[x][y] = result? "T" : "F";
        
        // 탈출 여부 리턴
        return result;
	}
}

* DFS 사용

* 기억 배열사용해서 시간 절약하기