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

오늘은 백준17090번 미로 탈출하기 문제를 풀어보도록 하자.

DFS와 DP를 섞은 문제다. 꽤나 까다로운 문제다. 무작정 모든 인덱스를 탐색하면 TLE가 나온다.

2번을 틀리고 맞았는데 TC는 잘 나왔지만 숨어있는 TC에서 왕창 틀린 것 같다.

dfs함수에서 조건을 잘못줘서 틀린걸 깨닫고 고쳐서 맞았다. 탐색과 dp를 섞은 문제는 항상 조심하며 풀어야겠다.

문제는 다음과 같다.

                               [접근법]

  1. 먼저 dp배열을 0으로 초기화해준다. (0 = 탐색을 아직 안 함, -1 = 탈출 불가, 1 = 탈출 가능으로 놓을 것이다.)
  
  2. for문을 돌려서 만일 탐색을 안한 곳(0) 이면 dfs함수를 실행한다.
  
  3. 그리고 거쳐간 곳의 dp값은 -1 (탈출불가)로 설정한다. 왜냐하면 탐색을 했으니 0은 아니고 탈출을 할 수 있다는 보장도 없으니 1도 아니다.
  그리고 동선이 겹치면, 즉 -1을 만나면 즉시 dp를 -1로 리턴해준다.
  
  4. 만일 탈출에 성공했으면 dfs를 1로 리턴해준다. 그리고 그 전의 dfs로 돌아와서 dp[y][x] = 1로 거쳐왔던 모든 길이 갱신된다.

                                     [코드]
#include <iostream>
using namespace std;

int R, C, answer = 0;
char map[500][500];
int dp[500][500] = { 0, }; //-1 = 탈출불가, 0 = 탐색안함, 1 = 가능
int dir[4][2] = { {-1,0}, {0,1},{1,0},{0,-1} };//북,동,남,서

bool check(int y, int x) {
	if (y < 0 || y >= R || x < 0 || x >= C) {
		return true;
	}
	return false;
}

int change_dir(char c) {
	if (c == 'U') {
		return 0;
	}
	else if (c == 'R') {
		return 1;
	}
	else if (c == 'D') {
		return 2;
	}
	return 3;
}

int dfs(int y, int x) {
	if (check(y,x)) {
		return 1;
	}
	if (dp[y][x] != 0) {
		return dp[y][x];
	}
	dp[y][x] = -1;
	int my = y + dir[change_dir(map[y][x])][0];
	int mx = x + dir[change_dir(map[y][x])][1];

	dp[y][x] = dfs(my, mx);
	
	return dp[y][x];
}

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

	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (dp[i][j] == 0) {
				int temp = dfs(i, j);
				if (temp == 1) {
					answer ++;
				}
			}
			else if (dp[i][j] == 1) {
				answer++;
			}
		}
	}
	cout << answer << '\n';
}