[BOJ 백준] 17090번 미로 탈출하기

문제

BOJ 17090 : https://www.acmicpc.net/problem/17090

17090번: 미로 탈출하기

접근

DFS를 이용하여 문제를 풀었다. 이때 주의할 점은 DFS를 통해 모든 경우의 수를 전부 돌아본다면 미로의 최대 크기가 500x500이므로 시간 초과가 날 것이다. 그렇다면 어떻게 해야 효율적으로 탐색할 수 있을까?

 

어떤 경로에 대해 탐색이 끝났다면 우리는 그 경로에 대한 답-더이상 나아갈 길이 없거나 미로를 탈출했거나-을 알고 있다. 이때 이 결과를 기억해주는 배열을 만들어주면 다른 좌표에서 출발하여 이미 탐색이 끝난 좌표에 진입하는 순간 우리는 더 가보지 않아도 이 길의 끝에 어떤 답이 있는지 알 수 있을 것이다. 이와 같은 방법을 메모이제이션(memoization)이라고 한다. 우리는 이 메모이제이션 기법을 이용하여 DFS의 탐색 시간을 대폭 단축할 수 있다. 이해가 어렵다면 아래의 사진을 참고하길 바란다.

메모이제이션(memoization)을 통해 탐색을 단축하는 과정

이렇게 이미 탐색한 경로에 대한 결과를 기억해두면 불필요한 탐색을 줄일 수 있을 것이다.

 

코드

// algorithm study
// BOJ_17090_미로 탈출하기

#include <iostream>
#include <vector>

using namespace std;

int n, m, visit[510][510] = {0}, dp[510][510] = {0}, answer = 0;
char map[510][510];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void dfs(int i, int j) {
    visit[i][j] = 1;
    int rx, ry;
    if (map[i][j] == 'D') {
        rx = i + dx[0];
        ry = j + dy[0];
    } else if (map[i][j] == 'U') {
        rx = i + dx[1];
        ry = j + dy[1];
    } else if (map[i][j] == 'R') {
        rx = i + dx[2];
        ry = j + dy[2];
    } else if (map[i][j] == 'L') {
        rx = i + dx[3];
        ry = j + dy[3];
    }

    if (visit[rx][ry] == 1) {
        dp[i][j] = 2;
    }
    if (rx < 0 || rx >= n || ry < 0 || ry >= m) {
        dp[i][j] = 1;
        answer++;
        return;
    } else if (dp[rx][ry] == 1) {
        dp[i][j] = 1;
        answer++;
        return;
    } else if (dp[rx][ry] == 2) {
        dp[i][j] = 2;
        return;
    } else {
        dfs(rx, ry);
        visit[rx][ry] = 0;
        if (dp[rx][ry] == 1)
            dp[i][j] = 1;
        else if (dp[rx][ry] == 2)
            dp[i][j] = 2;
    }
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (dp[i][j] == 2)
                continue;
            dfs(i, j);
            visit[i][j] = 0;
        }
    }

    cout << answer;
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study