[백준] 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개의 줄에는 미로의 각 칸에 적힌 문자가 주어진다.

출력

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

 

이 문제를 풀기 위해서는 재귀의 특성을 알고 있어야 한다.

모르는 상태에서 이 문제의 코드를 봐봤자 1차원적으로 생각할 수 밖에 없다.

 

예를 들어

 

특정 메서드가 있다고 가정하자.

파라미터가 있고, 리턴이 있다. 그러면 자연스럽게 리턴된 값을 출력할 수 있다.

여기서 주의 할점은 한개만 출력할때는 이래도 상관없지만.

메서드가 메서드를 부른다면

매서드 위에 메서드가 있는 그림이 된다. 그렇다는 이야기는 맨밑에 깔린 메서드의 값에 따라 위 메서드의 값도 영향이 생긴다는 이야기로 들린다.

이게 바로 재귀의 스택성질이다. 정확히 말하면 재귀도 스택처럼 쌓여지는 특성을 가지고 있다.

스택과 다른점은 재귀는 끝이 무엇인지 알려줘야한다는 점? 

 

이제 이 문제의 코드를 보면서 설명하도록 하겠다.

#include <bits/stdc++.h>
using namespace std;
int N,M;
char maps[501][501];
int v[501][501];

int go(int x,int y) {

  if (x < 0 || N <=  x || y < 0 || M <= y) return 1;

  if (v[x][y] != -1) return v[x][y];

  v[x][y] = 0;
  if (maps[x][y] == 'U') {
      v[x][y] = go(x-1,y);
  } 

  if (maps[x][y] == 'R') {
    v[x][y] = go(x,y+1);
  }

  if (maps[x][y] == 'D') {
    v[x][y] = go(x+1,y);
  }

  if (maps[x][y] == 'L') {
    v[x][y] = go(x,y-1);
  }

  return v[x][y];

}

int main(void) {
  cin >> N >> M;

  for(int i = 0;i<N;i++) {
    for(int j = 0; j<M;j++) {
      cin >> maps[i][j];
      v[i][j] = -1;
    }
  }

  int ans = 0;
  for(int i = 0; i<N;i++) {
    for(int j = 0; j<M;j++) {
      go(i,j);
      if (v[i][j]  == 1) ans +=1;
    }
  }

  cout << ans;

} 

코드를 보면 왜 1을 리턴하는지 의문이 들수 있다. 아까도 말했지만 이건 재귀의 특성이므로 처음에는 그냥 무시해도 된다. 다만 탈출조건이 성립 되는 즉시, 저 코드는 무시하면 안되는 코드가 되긴하지만 말이다.

 

사실 이 문제는 코드보다 그림으로 보여주는게 편할 것 같다. 하지만 ppt는 귀찮으니 그냥 글로 그리도록 하겠다.

 

예제 2번을 그림으로 그려 보자

 

DDR                  2번을 보면 이렇게 되어 있다.

DLU                 

LLL                     g(0 0) g(0 1) g(0 2)

                         g(1 0) g(1 1) g(1 2)

                         g(2 0) g(2 1) g(2 2)

 

대충 이런식으로 리턴이 된다. 물론 maps로 그리는게 더 정확하지만 말이다. 아무튼

 

 

근데 이게 더 힘들어서 그림판으로 그려봅시다.ㅎㅎ

D은 빨강색 L 초록색 U 파랑색 R은 노랑색으로 표시하겠습니다.

 

대충 이렇게 그려지는데 딱 봐도 직접적으로 탈출하는 녀석들은 두개 밖에 없다는 걸 확인 할 수 있습니다.

그러면 이들의 값은 1이고 나머지는 -1입니다. 아직 탈출혹은 탈출이 안 되는 지 모르기 때문입니다.

이런 의문이 들수 있습니다. 0,0부터 값을 넣는데 어째서 마지막부터 값을 추가하는지에 대해 의문을 가질 수 있습니다. 아까도 말했듯이 (죄송합니다) 재귀의 특성상 값이 저장이 됩니다. 그래서

if (v[x][y] != -1) return v[x][y];

이 코드가 존재하는 이유도 그 때문입니다. 그러면 전부 -1이기 때문에 값을 리턴을 시키지 않습니다. 물론 밑에 리턴이 있긴하지만 일단 무시하도록 하겠습니다. 일단 확실한건 이 리턴보다 값을 재귀시키는 부분이 더 위에 있기 때문에 탈출 조건을 넣지 않는 이상 폴더 안에 파일이 저장되있듯이 재귀안에 아직 풀리지 않는 메서드들이 저장되어있습니다.

 

또, 알아야할게..

v[x][y] = go(x-1,y);

이 녀석들인데 이 문제의 핵심이죠... 만약 이동한 값이 1이라면 v[x][y]도 값이 1이됩니다.

근데 만약 탈출하지 못했다면 어차피 우리는 코드에서 0으로 초기화를 시켰습니다. 0으로 초기화 시키는 이유는 이제 더이상 움직일 수 없다는 것을 의미합니다. 근데 왜 하냐고요?

이게 가능한것도 재귀때문인데... 탈출하지 않는이상 모든 곳은 0이 됩니다. 또,

직접적으로 탈출하는 곳을 제외하고 어느 위치에서든 당장 탈출이 불가능합니다. 그러니까 다른 곳의 영향이 필요합니다.

 

마지막으로 막줄 return에 대해 말하겠습니다. 하지만 이 부분은 확실하지 않습니다. 그래서 예상한것을 공유하려고 합니다. 마지막의 역할은 아마 확실 여부를 체크하는 것 같습니다. 값이 변하면 안되기 때문이죠. 또, 메서드가 int를 반환하라고 했으니 어쩔 수 없는걸까요?

 

 

아 근데 왜 bool이 아니냐 라고 생각할 수 있는데 여기서는 상태값이 3개여야 하기 때문입니다.

-1 : 안 움직임

0 : 못 움직임(당장)

1 : 탈출 가능 ㅎㅎ

이렇게 입니다. 그래서 bool은 힘듭니다. 될수도 있겠지만 말이죠..

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

bool visited[505][505];
char input[505][505];
int cache[505][505];

int N, M;

bool isinside(int a, int b) {
    if (a<1 || a > N || b < 1 || b > M) return false;
    return true;
}

int dfs(int a, int b) {
    if (!isinside(a, b)) return 1;

    int& ret = cache[a][b];

    if (ret != -1) return ret;

    ret = 0;

    if (input[a][b] == 'U') {
        return ret = dfs(a - 1, b);
    }
    if (input[a][b] == 'R') {
        return ret = dfs(a, b + 1);
    }
    if (input[a][b] == 'D') {
        return ret = dfs(a + 1, b);
    }
    if (input[a][b] == 'L') {
        return ret = dfs(a, b - 1);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    memset(input, 0, sizeof(input));
    memset(cache, -1, sizeof(cache));

    //ifstream cin;
    //cin.open("input.txt");

    cin >> N >> M;

    for (int i = 1; i <= N; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < M; ++j) {
            input[i][j + 1] = s[j];
        }
    }

    int cnt = 0;
    int loop = 0;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            cnt += dfs(i, j);
        }
    }

    printf("%d", cnt);

    return 0;
}