[백준 17090] 미로 탈출하기

분류 

dp

요구사항

주어진 맵에서 탈출 가능한 정점이 몇개인가 고르는 문제

풀이

모든 정점에 대해서 dfs 실시하면 500*500*500 이 되므로 안된다

이미 방문한 정점은 방문하지 않고 이전 결과를 활용할 수 있는 dp로 풀자는 결론은 금방 나왔다

하지만 구현이 어려웠다.

 

평소 메모리제이션 처럼 -1로 초기화 후, 첫 방문시 0으로 실시하고

다시 최종 값을 ref에 넣어주어야한다.

 

아래 코드를 참조한다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <string.h>
#include <queue>

using namespace std;
int n, m;
char map[550][550];
int visit[550][550];
int ans = 0;
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
int get_dir(char ch) {
	if (ch == 'U') return 0;
	else if (ch == 'L') return 1;
	else if (ch == 'D') return 2;
	else if (ch == 'R') return 3;
}
int solve(int r, int c) {
	if (visit[r][c] != -1) return visit[r][c];
	int &ref = visit[r][c];
	visit[r][c] = 0;
	int d = get_dir(map[r][c]);
	int nr = r + dr[d];
	int nc = c + dc[d];
	if (nr < 0 || nc < 0 || nr >= n || nc >= m) return ref = 1;;
	visit[r][c] = solve(nr, nc);
	return ref;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf(" %c", &map[i][j]);
			visit[i][j] = -1;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			ans +=solve(i, j);
		}
	}
	cout << ans << endl;
}