[BOJ] 17090번 미로 탈출하기 (C++)

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

17090번: 미로 탈출하기

 

#include <iostream>
using namespace std;
 
int n, m;
char map[500][500];
int dp[500][500];
int answer;
 
int dfs(int x, int y) {
	if (x < 0 || x >= n || y < 0 || y >= m) return 1;
	if (dp[x][y] != -1) return dp[x][y];
 
	dp[x][y] = 0;
 
	int nx, ny;
	if (map[x][y] == 'U') {
		nx = x - 1;
		ny = y;
	}
	else if (map[x][y] == 'R') {
		nx = x;
		ny = y + 1;
	}
	else if (map[x][y] == 'D') {
		nx = x + 1;
		ny = y;
	}
	else {
		nx = x;
		ny = y - 1;
	}
 
	dp[x][y] = dfs(nx, ny);
 
	return dp[x][y];
}
 
int main() {
	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;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			answer += dfs(i, j);
		}
	}
	cout << answer;
	return 0;
}

 

dfs + 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배열의 값 그대로 리턴시켜주면서 중복된 탐색을 없앴다.