백준 17090 - 미로 탈출하기

[문제 바로가기]

 

1. 유형

dfs, 동적프로그래밍

 

2. 문제 분석

 

2-1. 설계

 

2-2. 설명

가장 먼저 떠오른 생각은 완전 탐색 입니다. 하지만 500^4을 하면 1억이 넘어가 시간초과가 나옵니다.

따라서 메모리제이션을 통해 한번 탐색한 길은 또 탐색하지 않도록 하는 방법으로 풀이했습니다.

 

범위를 나가서 한번 검증된 길은 1을 저장하고, 잘못된 길은 0을 리턴해서

굳이 끝까지 가지 않더라도 길의 종착지가 어떤지를 확인 가능합니다.

 

3. 코드

import java.util.*;
import java.io.*;

public class Main {
	static int N,M, dp[][];
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		char map[][] = new char[N][M];
		dp = new int[N][M];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			String s = st.nextToken();
			map[i] = s.toCharArray();
		}
		int cnt=0;
		int visit[][]=new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(visit[i][j]==0) {
					visit[i][j]=1;
					dp[i][j]=dfs(i, j, visit, map);
				}
			}
		}
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(dp[i][j]==1)
					cnt++;
			}
		}
		System.out.println(cnt);
	}
	static int dfs(int r, int c, int visit[][], char map[][]) {
		if(map[r][c]=='U') {
			r--;			
		}else if(map[r][c]=='R') {
			c++;
		}else if(map[r][c]=='D') {
			r++;
		}else if(map[r][c]=='L') {
			c--;
		}
		if(r<0 || r>=N || c<0 ||c>=M) {
			return 1;
		}
		if(visit[r][c]==1) {
			if(dp[r][c]==0) {
				return 0;
			}else {
				return 1;
			}
		}else {
			visit[r][c]=1;
			dp[r][c]= dfs(r, c, visit, map);
			return dp[r][c];
		}
	}
	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}