백준 17090번 : 미로 탈출하기 C++ 문제 풀이

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

17090번: 미로 탈출하기

1.문제설명

3 4
RRDD
RRDR
DULU

 

17090 규칙

모든 점에 대해서 각 점으로부터 출발 할 때

다음 규칙으로 이동하여 미로 밖으로 탈출할 수 있는 점의 개수를 구하는 문제다.

17090 설명

이동 과정을 나타냈을 때 빨간색 같은 경우는 탈출할 수 없고

파란색은 탈출 할 수 있는 경로이다.

위 미로의 특성 상 같은 경로 상에 있다면 같은 결괏값을 가지게 된다.

 

2. 접근방법[알고리즘]

DFS로 메모리제이션을 해주면서 탈출할 수 있는지 없는지를 구해주어야한다.

 

1.DFS를 수행하기전 초기값으로 모든 좌표에 -1을 저장한다.

2.DFS를 수행하면서 방문한 점에는 0을 저장한다.

3.DFS 수행 결과 탈출에 성공한다면 탈출 경로까지 지나는 모든 점에 1을 저장한다.

4. DFS를 돌면서 현재 좌표에 -1이 저장되어 있지 않다면 탈출이 가능한지 불가능한지 이미 구해졌으므로

그 값을 리턴해준다.

 

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;
//방문한 곳을 다시 방문하면 종료
int n, m, ans, dy[503][503];
char arr[503][503];

int DFS(int x, int y) {
	char a = arr[x][y];
	// 미로 탈출
	if (a == '\0') return 1;

	int& cur = dy[x][y];
	//x,y가 이미 방문한 점이라면 
	if (cur != -1) {
		return cur;
	}
	// 방문 표시
	cur = 0;
	if (a == 'U') {
		cur = DFS(x - 1, y);
	}
	else if (a == 'R') {
		cur = DFS(x, y + 1);
	}
	else if (a == 'D') {
		cur = DFS(x + 1, y);
	}
	else if (a == 'L') {
		cur = DFS(x, y - 1);
	}

	return cur;
}

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

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
			dy[i][j] = -1;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ans += DFS(i,j);
		}
	}
	cout << ans <<'\n';
}

백준 17090 메모리 및 시간 

시간 초과 이유

지나가는 점에 대해서도 결괏값을 저장해주어야 하는데,

점 하나 하나 for 문을 돌 때마다 따로 처리해줘서 시간이 초과되었다.

메모리제이션이 중요한 문제다.