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

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

17090번: 미로 탈출하기

 

 

오늘은 Gold 2 난이도를 가지는 미로 탈출하기 문제 풀이를 하려고 합니다.

Gold 2난이도라고 해서 큰 맘먹고 문제를 풀었는데, 생각외로 10분만에 문제를 풀어버렸습니다..

대단한건아니지만....문제 길이도 짧고 규칙성을 바로 찾아서 바로 풀게 되었습니다.

 

문제에서 각 적힌 칸에서 U, R, D, L, 문자 그대로 (Up, Right, Down, Left)방향으로 이동해서 미로를 탈출하면 count ++를 해주는 방식입니다.

 

입력이 500 X 500이고, 각 칸마다 미로 탈출을 수행하면 시간이 어마어마하게 초과될 것이라고 생각해서

처음에 다이나믹을 생각했었습니다.  다이나믹으로 갔던 길에 대한 정보를 memorizaiton을 하면 되겠다고 생각했습니다.

 

갔던 길은 무조건 탈출의 길로 인도되어지기 때문에, 성공했던 길에 대해서는 모두 성공했다는 표시를 해주면 되죠.

마치, 헨델과그레텔처럼 빵가루를 남겨서 빵가루가 있는 부분은 아 성공이구나! 하고 무조건 count++하고 넘어가면

시간 세이브를 엄청나게 할 수 있다는 것입니다!!!!!!

 

단, 갔던 길을 계속 돌아버리는 무한루프를 주의하셔야 합니다. 이 경우에도 빵가루 종류 중에서 갔던 길을 표시하는 빵가루를 남기면 이건 무한 루프네!? 라고 생각하고 바로 빠져 나올 수 있죠.

 

코드로 설명해드리겠습니다.~

 

for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {   // 0, 0부터 n-1, m-1까지 각 각 공간이 탈출가능한지 확인하기
			int x = i;                  // i값을 x에 대입
			int y = j;                  // j값을 y에 대입

			deque<pair<int, int>> dq;   // 이 덱은 갔던 길을 남기는 빵가루를 놓아야할 좌표 역할을 해줌. 만약에 미로 탈출을 성공했으면, 하나씩 pop하면서 빵까루를 뿌려주면됨

			bool impos_FLAG = false;    // 왔던 길이거나 갈 수 없는 상황이라면  impossible FLAG 를 true로 바꿔줌, 나중에 count++를 안해주기 위해서.

			while (0 <= x && x < n && 0 <= y && y < m) {  // 미로에 있으면 계속 수행.

				if (map_status[x][y] == 1) break;         // 1값은 성공했던 길이기 때문에 무조건 count++, impos_FLAG가 초기값 false이기 때문에 count++를 해주게 되어있다.
				else if (map_status[x][y] == 2 || map_status[x][y] == 3) { // 2는 불가능 길, 3은 왔던 길
					impos_FLAG = true;         // 불가능과 왔던 길이라면 imposs_FLAG 을 true선언해주고 while문 빠져나오기
					break;
				}

			
				char temp = map_c[x][y];      // 방향은 어디로 가야합니까?

				dq.push_back(make_pair(x, y)); // 성공한다면 빵가루를 남겨야하기 때문에 일단 덱에다가 왔던 좌표들 다 담아주기
				map_status[x][y] = 3;          // 이 길은 이미 지니갔어요~~ 만약 성공한다면 덱에있는 빵가루를 다시 뿌려줘서 1로 바꿔주겠죠?

 

코드를 보시면, 0, 0부터 n-1, m-1까지 for문을 돌면서 이 칸으로 출발해서 미로를 탈출 할 수 있는지에 대한 코드의 첫부분 입니다.

 

deque을 선언한 이유는, 만약에 미로를 탈출했다면 탈출한 경로를 임시적으로 저장하기 위해서 입니다. 

탈출하고 나서 deque를 하나씩 pop하면서 미로에 빵가루를 남길 수 있죠. 그 다음부터 빵가루만 보게 되면 무조건 와~ 이건 전에 성공했던 길이구나. 무조건 성공이네? 하고 다음으로 넘어가면 시간을 엄청나게 줄일 수 있다는 겁니다.

 

while문은 안에서 놀고 있다면 계속 돌리겠다는 의미지만, 무한루프가 안도는 이유가, 갔던 길을 표시해서 갔던 길을 만나면, 아! 이게 무한루프를 돌 수 밖에 없는 루트구나 하고 밖으로 빠져나옵니다.

 

map_status[x][y] =3 은 왔던 길을 표시해주는 역할을 합니다. map_status[x][y]에 3을 표시하더라도, 이 경로가 성공한 경로라면 나중에 deque에서 다시 1로 만들어 주기 때문에 3으로 왔던 길을 표시해도 상관없습니다. 

 

 

				if (temp == 'U') {

					x = x + dx[0];
					y = y + dy[0];
					

				}

				else if (temp == 'R') {
					x = x + dx[1];
					y = y + dy[1];
				}

				else if (temp == 'D') {
					x = x + dx[2];
					y = y + dy[2];

				}

				else if (temp == 'L') {
					x = x + dx[3];
					y = y + dy[3];

				}



			
			}

			if (!impos_FLAG) {           // impos_FLAG 즉, 불가능하다고 표시안해주면 덱에서 좌표를 하나씩 빼면서 빵가루 뿌려주기, count++해서 가능하다고 카운트 추가해주기

				while (!dq.empty()) {

					int dq_x = dq.back().first;
					int dq_y = dq.back().second;

					map_status[dq_x][dq_y] = 1;
					dq.pop_back();
				}

				result++;
			}

 

 

그 다음은, 각 칸에 위치의 방향을 구해서 그 방향대로 이동하는 것 입니다. NxM 을 벗어나게 되면 while문에 의해서 빠져나오겠죠. 만약에 정상적으로 잘 빠져나온거라면 impos_FLAG가 false가 될거기 때문에 if(!impos_FLAG)에 들어가게 됩니다. 

 

아까 말씀드린대로, deque에 성공한 루트를 임시적으로 저장해놨기 때문에 하나씩 pop하면서 지나왔던 길을 빵가루로 뿌려준다면, 다음에 빵가루를 만날 때.. 아 내가 아는 길이구나! 하고 바로 while문을 빠져나올 수 있기에 시간을 엄청나게 세이브 해줍니다.

 

다이나믹이라는 알고리즘이 큰 문제를 작은 문제로 나누어서 점점점 큰 문제를 해결해가는 것인데, 이건 작은 문제로 큰 문제로 갔다고 보기에는 조금 어렵다고 생각이 듭니다. 

중복을 피하기 위한 체크 표시라고 생각하기 때문에, 제가 처음에 생각했던 다이나믹과는 사뭇 다른 방법입니다.

 

다이나믹으로 방법의 개수를 구하라고 했더라면, 이전의 값들을 누적시켜서 구했을 것 같습니다.

하지만, 이 문제는 count만 세는거기 때문에 check배열로 풀었다는 걸로만...ㅎ

 

전체코드는 다음과 같습니다.

 

#include <iostream>
#include <deque>

using namespace std;

#define input_max 500 + 1

int n, m;
char map_c[input_max][input_max];
int map_status[input_max][input_max]; // 0은 모름 unkown, 1은 가능, 2는 불가능, 3은 갔던 길

int dx[] = { -1, 0, 1, 0 }; // 상우하좌
int dy[] = { 0, 1, 0, -1 };

int result;

void solution() {

	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			cin >> map_c[i][j];
		}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			int x = i;
			int y = j;

			deque<pair<int, int>> dq;

			bool impos_FLAG = false;

			while (0 <= x && x < n && 0 <= y && y < m) {

				if (map_status[x][y] == 1) break; 
				else if (map_status[x][y] == 2 || map_status[x][y] == 3) {
					impos_FLAG = true;
					break;
				}

			
				char temp = map_c[x][y];

				dq.push_back(make_pair(x, y));
				map_status[x][y] = 3;

				if (temp == 'U') {

					x = x + dx[0];
					y = y + dy[0];
					

				}

				else if (temp == 'R') {
					x = x + dx[1];
					y = y + dy[1];
				}

				else if (temp == 'D') {
					x = x + dx[2];
					y = y + dy[2];

				}

				else if (temp == 'L') {
					x = x + dx[3];
					y = y + dy[3];

				}



			
			}

			if (!impos_FLAG) {

				while (!dq.empty()) {

					int dq_x = dq.back().first;
					int dq_y = dq.back().second;

					map_status[dq_x][dq_y] = 1;
					dq.pop_back();
				}

				result++;
			}


		}


	cout << result << '\n';
}


int main() {


	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	solution();


	return 0;
}