[ 백준 17090 ] 미로 탈출하기 (C++)

백준의 미로 탈출하기(17090) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 주어진 맵에서 경계 밖으로 이동할 수 있는 칸의 갯수를 찾아야 하는 문제이다.

   먼저, 모든좌표에서 주어진 방향에 맞게 따라가면서 하나하나 탐색을 하게 되면 시간초과가 발생하게 된다.

   최악의 경우, 500 x 500 크기의 맵에서 500 x 500 만큼의 탐색을 해야 할 수도 있기 때문이다.

   따라서 250000 x 250000 번의 탐색은 제한시간인 1초 내에 들어올 수가 없다.

   그래서 본인은 메모이제이션을 사용했다.

   DFS + DP를 이용해서 풀었는데, 이를 풀기위해서 int DP[][] 라는 배열을 만들어 주었다.

   DP 배열에는 -1, 0, 1 3개의 값만을 저장해주었는데

   DP[a][b] = -1 의 의미는 "아직 (a, b)에서는 탐색을 안해봤으니 탐색을 해봐야 합니다" 를 의미하고

   DP[a][b] = 0 의 의미는 "(a, b)를 탐색해 봤는데, (a, b)에서는 밖으로 나갈 수 없습니다." 를 의미하고

   DP[a][b] = 1 의 의미는 "(a, b)를 탐색해 봤는데, (a, b)에서는 밖으로 나갈 수 있습니다." 를 의미한다.

   즉, 초기에는 모든 DP배열의 값이 -1로 초기화 되어있고, DFS로 탐색을 진행하면서 DP배열의 값이 -1이 아니라면

   그대로 DP배열의 값 그대로 return을 시켜줌으로써 중복된 탐색을 없애주었다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 500
using namespace std;
 
int N, M, Answer;
int DP[MAX][MAX];
bool Visit[MAX][MAX];
char MAP[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Dir_To_Idx(char A)
{
    if (A == 'U') return 3;
    else if (A == 'R') return 0;
    else if (A == 'D') return 2;
    else if (A == 'L') return 1;
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> MAP[i][j];
            DP[i][j] = -1;
        }
    }
}
 
int DFS(int x, int y)
{
    if (x < 0 || y < 0 || x >= N || y >= M) return 1;
    if (DP[x][y] != -1) return DP[x][y];
    
    DP[x][y] = 0;
    int Dir = Dir_To_Idx(MAP[x][y]);
 
    DP[x][y] = DFS(x + dx[Dir], y + dy[Dir]);
 
    return DP[x][y];
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            Answer = Answer + DFS(i, j);
        }
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}