백준 17090번: 미로 탈출하기

문제 설명

• https://www.acmicpc.net/problem/17090
• 미로에서 탈출 가능한 칸의 수를 계산해야 합니다.
  모든 움직임은 칸에 적힌 방향으로 이동해야 합니다.

접근법

• DFS와 int형태의 visit배열을 활용했습니다.
  DFS로 방문한 경로를 cnt로 채운 뒤 마지막에 도착한 위치가 1. 탈출한 곳인지, 2. 싸이클인지, 3. 이미 방문한 적 있는 경로인지를 판단합니다.
• 이미 방문한 적이 있는 곳인가를 판별하는 코드를 비효율적으로 설계해서 시간초과가 많이 났었습니다.
  • 가장 처음에는 possibleList,impossibleList를 따로 만든 뒤 contains()로 계산했었습니다.
  • 이후 시간을 줄이기 위해 <Integer,Boolean>형태의 map을 만들어 계산했었습니다.
  • 단순한 1차원 배열이 가장 좋습니다. boolean[] canEscape = new boolean[N*M+1];

정답

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

public class Main {
	static int[] dx = {0,1,0,-1}; // R, D, L, U
	static int[] dy = {1,0,-1,0};
	static boolean[] canEscape;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		char[][] board = new char[N][M];
		for (int i = 0; i < board.length; i++) {
			board[i] = br.readLine().toCharArray();
		}
		canEscape = new boolean[N*M+1];
		int[][] v = new int[N][M];
		int answer = 0;
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(v[i][j] != 0) {
					if(canEscape[v[i][j]]) answer++;
				}else {
					v[i][j] = ++cnt;
					DFS(N,M,new int[] {i,j},v,board,cnt);
					if(canEscape[v[i][j]]) answer++;
				}
			}
		}
//		for (int i = 0; i < v.length; i++) {
//			System.out.println(Arrays.toString(v[i]));
//		}
		System.out.println(answer);

	}
	
	public static void DFS(int N, int M, int[] now, int[][] v, char[][] board, int cnt) {

		int d = Direction(board[now[0]][now[1]]);
		int nx = now[0]+dx[d];
		int ny = now[1]+dy[d];
		if(0 > nx || nx >= N || 0 > ny || ny >= M) {
			canEscape[cnt] = true;
			return;
		}
		
		if(v[nx][ny] !=0) {
			if(v[nx][ny] == cnt) {
				canEscape[cnt] = false;
				return;
			}else {
				if(canEscape[v[nx][ny]]) {
					canEscape[cnt] = true;
				}else {
					canEscape[cnt] = false;
				}
				return;
			}
		}
		if(0 <= nx && nx < N && 0 <= ny && ny < M && v[nx][ny] == 0) {
			v[nx][ny] = cnt;
			DFS(N,M,new int[] {nx,ny},v,board,cnt);
		}
		
	}

	public static int Direction(char c) {
		if(c == 'R') return 0;
		else if(c == 'D') return 1;
		else if(c == 'L') return 2;
		else return 3;
	}
}