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

17090번 : 미로 탈출하기

---

문제)

크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다.

어떤 칸(r, c)에 적힌 문자가

• U인 경우에는 (r-1, c)로 이동해야 한다.
• R인 경우에는 (r, c+1)로 이동해야 한다.
• D인 경우에는 (r+1, c)로 이동해야 한다.
• L인 경우에는 (r, c-1)로 이동해야 한다.

미로에서 탈출 가능한 칸의 수를 계산해보자. 탈출 가능한 칸이란, 그 칸에서 이동을 시작해서 칸에 적힌대로 이동했을 때, 미로의 경계 밖으로 이동하게 되는 칸을 의미한다.

 

 

 

입력 :

첫째 줄에 미로의 크기 N, M(3 ≤ N, M ≤ 500)이 주어진다. 둘째 줄부터 N개의 줄에는 미로의 각 칸에 적힌 문자가 주어진다.

 

 

 

출력 :

첫째 줄에 탈출 가능한 칸의 수를 출력한다.

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
#include <string>
#include <climits>
 
using namespace std;
 
int n, m;
vector<string> vec;
vector<vector<int>> dp;
int visited[510][510];
 
int recur(int a, int b, int cnt)
{
    int ret = INT_MAX;
 
    // 미로를 벗어났다면 0을 리턴해준다.
    if (0 > a || a >= n) return 0;
    if (0 > b || b >= m) return 0;
 
    // 이미 방문한 곳이라면 dp[a][b]를 리턴한다.
    if (dp[a][b] != -1)    return dp[a][b];
 
    // 이미 방문했던 곳을 또 방문한다면
    // 사이클이 생긴다는 것이므로
    // 나올 수 없는 값을 리턴해준다.
    if (visited[a][b] == 1)    return INT_MAX;
 
    // 현재 위치를 방문처리한다.
    visited[a][b] = 1;
 
    // 각 문자에 따라 이동한 것중 최솟값을 ret에 저장한다.
    if (vec[a][b] == 'U') ret = min(ret, recur(a - 1, b, cnt + 1) + 1);
    if (vec[a][b] == 'R') ret = min(ret, recur(a, b + 1, cnt + 1) + 1);
    if (vec[a][b] == 'D') ret = min(ret, recur(a + 1, b, cnt + 1) + 1);
    if (vec[a][b] == 'L') ret = min(ret, recur(a, b - 1, cnt + 1) + 1);
    
    dp[a][b] = ret;
 
    return dp[a][b];
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
    dp.resize(n, vector<int>(m, -1));
 
    string temp;
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        vec.push_back(temp);
    }
 
    int result = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (dp[i][j] == -1) recur(i, j, 0);
            if (dp[i][j] == INT_MAX) continue;
            if (dp[i][j] > 0) result++;
        }
    }
 
    cout << result;
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/17090 

17090번: 미로 탈출하기