문제

BOJ 17090: 미로 탈출하기 https://www.acmicpc.net/problem/17090

풀이

조건

• 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있다.
• 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다.
  • U인 경우에는 (r-1, c)로 이동해야 한다.
  • R인 경우에는 (r, c+1)로 이동해야 한다.
  • D인 경우에는 (r+1, c)로 이동해야 한다.
  • L인 경우에는 (r, c-1)로 이동해야 한다.
• 미로에서 탈출 가능한 칸의 수를 계산한다.
• 탈출 가능한 칸이란, 그 칸에서 이동을 시작해서 칸에 적힌대로 이동했을 때, 미로의 경계 밖으로 이동하게 되는 칸을 의미한다.

풀이 순서

• 기본적으로 DFS를 사용해 미로를 탈출할 수 있는지 확인한다.
  • 미로 범위를 벗어나면 탈출한 것이다.
• 시간복잡도를 고려하여 DP의 방법을 함께 사용한다.
  • 이미 탈출할 수 있다고 기록된 위치에 도달하면 더 이상 탐색하지 않고 탈출할 수 있다고 판단한다.
    
    
• 모든 방문하지 않은 위치에서 DFS 수행
• 다음 위치 확인
  • 미로를 벗어남 -> 탈출
    • 지나온 모든 경로 true 기록
  • 아직 미로 안
    • 아직 방문하지 않은 위치
      • 방문처리하고 DFS 재귀 호출
    • 이미 방문한 위치
      • 탈출 가능한 경로에 있는 위치 -> 지나온 경로도 모두 탈출 가능한 경로
        • 지나온 모든 경로 true 기록
      • 탈출 불가능한 경로에 있는 위치 -> 지나온 모든 경로 탈출 불가능
        • 지나온 모든 경로 false 기록

코드

Java

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

public class Main {

	static int N, M;
	static int[][] board; // 원본 미로
	static boolean[][] dp; // 탈출가능한 경로인지 메모이제이션 해놓을 배열

	static int[] dx = { -1, 0, 1, 0 };
	static int[] dy = { 0, 1, 0, -1 };

	static int answer;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		board = new int[N][M];
		// 미로에 적힌 문자를 숫자로 된 방향으로 매핑한다.
		for (int i = 0; i < N; i++) {
			String input = br.readLine();
			for (int j = 0; j < M; j++) {
				char c = input.charAt(j);
				if (c == 'U') {
					board[i][j] = 0;
				} else if (c == 'R') {
					board[i][j] = 1;
				} else if (c == 'D') {
					board[i][j] = 2;
				} else if (c == 'L') {
					board[i][j] = 3;
				}

			}
		}

		answer = 0;
		dp = new boolean[N][M];
		boolean[][] isVisited = new boolean[N][M];
		// 모든 위치를 확인
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				// 아직 방문한 적 없는 위치면 탐색 시작
				if (!isVisited[i][j]) {
					// 방문 처리하고 dfs 시작
					isVisited[i][j] = true;
					dp[i][j] = dfs(i, j, isVisited);
				}
			}
		}

		// dp 배열에 true 체크된(탈출 가능한) 위치가 몇 개 인지 카운트
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (dp[i][j]) {
					answer += 1;
				}
			}
		}

		System.out.println(answer);
	}

	static boolean dfs(int x, int y, boolean[][] isVisited) {
		// 현재 위치의 방향
		int dir = board[x][y];
		// 다음 위치
		int nx = x + dx[dir];
		int ny = y + dy[dir];

		// 탈출 가능하면 true 반환
		if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
			return true;
		}
		// 이미 방문했던 위치라면
		if (isVisited[nx][ny]) {
			// 메모이제이션 된 결과를 확인
			// 탈출 가능하다고 메모이제이션 됐다면 true 반환
			if (dp[nx][ny]) {
				return true;
			}
			// 탈출 불가능하다고 메모이제이션 됐다면 false 반환
			else {
				return false;
			}
		}
		// 아직 방문한 적 없는 위치라면
		else {
			// 현재 위치 방문 처리하고 dfs 재귀 호출 -> dp에 탈출 여부 기록
			isVisited[nx][ny] = true;
			dp[nx][ny] = dfs(nx, ny, isVisited);
			// dp에 기록된 탈출여부 반환
			return dp[nx][ny];
		}
	}

}

정리

• 처음에 단순히 bfs와 dfs로 탈출여부만 확인해보려다 시간초과가 났다.
• DP를 이용해 탈출 여부를 기록해 시간을 줄일 수 있었다.