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

문제 링크: https://www.acmicpc.net/problem/17090

17090번: 미로 탈출하기

1. 주의할 점

- DFS를 통해 구현이 가능하지만, 메모라이즈 기법과 함께 사용하지 않으면 TLE가 발생한다

- 메모라이즈에 사용될 Visit배열을 -1로 초기화한다

 

2. 구현

- 모든 행과 열에 대해서 Visit배열의 값이 -1이 아니라면 DFS탐색을 시작한다

- DFS의 경우, 이미 방문한 적이 있다면(Visit값이 -1이 아닌경우) 해당 Visit배열의 값을 반환한다(메모라이즈 기법)

- 아직 방문한 적이 없다면, Visit갑을 0으로 넣고 해당 칸에 있는 문자에 대해 작업을 수행한다.

- 만약 이동하려는 곳이 범위 밖이라면 Visit값을 1로 바꾸고 Return 한다

 

#include <iostream>
using namespace std;
char arr[500][500];
int visit[500][500];		//-1: 방문 x, 0: 못나간다, 1: 나간다
int row, col, result = 0;

int dfs(int y, int x) {
	if (visit[y][x] != -1) return visit[y][x];		//나가거나 나가지 못하는 경우
	char c = arr[y][x];
	int temp = 0;
	visit[y][x] = 0;
	if (c == 'U') {
		if (y == 0) 	temp = 1;
		else	temp = dfs(y - 1, x);
	}
	else if (c == 'D') {
		if (y == row - 1) 	temp = 1;		
		else	temp = dfs(y + 1, x);
	}
	else if (c == 'L') {
		if (x == 0) temp = 1;		
		else	temp = dfs(y, x - 1);
	}
	else if (c == 'R') {
		if (x == col - 1) 	temp = 1;		
		else	temp = dfs(y, x + 1);
	}
	visit[y][x] = temp;
	return temp;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> row >> col;
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {
			cin >> arr[i][j];
			visit[i][j] = -1;
		}

	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) 
			if (visit[i][j] == -1) 
				dfs(i, j);

	for (int i = 0; i < row; i++) 
		for (int j = 0; j < col; j++)
			if (visit[i][j] == 1)
				result++;
	cout << result;
	system("pause");
	return 0;
}