[백준] 17090 미로 탈출하기

1. 문제

www.acmicpc.net/problem/17090

17090번: 미로 탈출하기

2. 접근방법

DFS와 메모리제이션을 활용한 문제

 

만약 어느 한 위치에서 경로를 따라가다

 

이미 방문 했던 곳을 또 가게 된다면 그 경로는 계속해서 순환하는 형태가 되어

나가지 못할 것이다.

순환 하지 않는다면 결국 언젠가는 밖으로 나갈 수 있게 된다.

 

어느 경로에서 왔던지 이미 밖으로 나간 전적이 있는 경로에 가면 그 경로도 모두 밖으로 나갈 수 있고

순환하는 전적이 있는 경로는 결국 모두 순환하게 되어 못나가게 될 것이다.

 

여기서 착안하여 dfs를 이용해 한 점에서 갈 수 있는데 까지 가보고

순환한다면 지금까지 온 모든 경로에 F를 저장

밖에 나갈 수 있다면 T를 저장하고

 

또 다른 점에서 경로를 찾아가다 T나 F를 만난다면 지금 껏 왔던 모든 경로에도 T나 F를 저장하여

모든 점에서 확인하면 O(N)에 해결이 가능하다.

 

---------------------

다른 방법으로 테두리만 검사하여 밖으로 나갈 수 있는 장소에서 거꾸로 찾아가며

T인 경로만 모두 찾는 방법도 있을 것 같은데 따로 구현은 안해봤다.

 

 

3. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class G2_17090미로탈출하기 {
	static char map [][];
	static boolean visit[][];
	static int N,M;
	public static void main(String[] args) throws Exception {
		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 char [N][M];
		visit = new boolean[N][M];
		for(int i = 0 ; i < N ; i++)
			map[i] = br.readLine().toCharArray();
		int cnt = 0;
		for(int i= 0 ; i < N ; i++) {
			for(int j = 0 ; j < M ; j++) {
				if(dfs(i,j))
					cnt++;
			}
		}
		System.out.println(cnt);
		
	}
	public static boolean dfs(int row, int col) {
		boolean result = false;
		if(row<0 || col <0 || row>=N || col>=M)
			return true;
		
		if(map[row][col] == 'T')
			return true;
		else if(map[row][col] == 'F')
			return false;
		
		if(visit[row][col]) {
			return false;
		}
		visit[row][col] = true;
		if(map[row][col] == 'D')
			result = dfs(row+1,col);
		else if(map[row][col] == 'U')
			result = dfs(row-1,col);
		else if(map[row][col] == 'R')
			result = dfs(row,col+1);
		else if(map[row][col] == 'L') 
			result = dfs(row,col-1);
		
		map[row][col] = result? 'T': 'F';
		return result;
		
		
	}
}

4. 마치며

처음 풀이할 때

2중 for문 안에 visit = new boolean[N][M]으로 초기화를 했었는데 시간 초과가 떳다

배열 초기화 하는데 많은 리소스가 들거라고 생각을 안했는데 시간초과가 떠서 당황했었음