문제 푼 날짜 : 2021-10-01

문제

문제 링크 : https://www.acmicpc.net/problem/17090

접근 및 풀이

DP와 DFS를 이용한 그래프 탐색문제이다.
문제에 입력으로 주어진 미로의 모든 위치에서 출발하여 탈출이 가능한지 DFS로 탐색해주었다.
탐색하면서 중요한건 메모이제이션을 활용하는 것이다. 이를 위해 dp 배열을 선언하였고, dp배열이 의미하는 것은 해당 인덱스에서 출발하였을 때 미로를 탈출할 수 있는지이다. (dp[x][y] = 1 일 때, (x, y)에서 시작하면 탈출 가능)
이를 이용하여 지도의 문자를 따라 탐색하면서 dp 배열을 업데이트시켜주었다.

처음에 visited 배열을 두고, 각 위치에서 dfs를 시작할 때마다 false로 업데이트 시켜주고 탐색을 시켰더니 시간초과가 났다...

코드

// 백준 17090번 : 미로 탈출하기
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int N, M;
vector<string> maze;
int dp[501][501];

int dfs(int y, int x) {
    if (y < 0 || y >= N || x < 0 || x >= M) {
        return 1;
    }
    int &ret = dp[y][x];
    if (ret != -1) {
        return ret;
    }
    ret = 0;

    switch (maze[y][x]) {
        case 'U' :
            ret = dfs(y - 1, x);
            break;
        case 'R' :
            ret = dfs(y, x + 1);
            break;
        case 'D' :
            ret = dfs(y + 1, x);
            break;
        case 'L' :
            ret = dfs(y, x - 1);
            break;
    }
    return ret;
}

int main() {
    cin >> N >> M;
    
    string str = "";
    for (int i = 0; i < N; i++) {
        cin >> str;
        maze.push_back(str);
    }
    memset(dp, -1, sizeof(dp));

    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (dfs(i, j) == 1) {
                ans++;
            }
        }
    }
    cout << ans;
    return 0;
}

결과

피드백

비슷한것 같으면서 다른 문제들이 많다. 문제를 더 많이 풀고 꼼꼼히 풀이를 복기해야겠다.