백준 17090 미로 탈출하기

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

17090번: 미로 탈출하기

 

[주의할 조건]

(r , c)에 적힌 문자에 따라서, 가야하는 방향이 정해져 있다.

 

[구하는 값]

그 칸에서 이동을 시작했을 때, 미로의 경계 밖으로 이동하게 되는 칸이 총 몇 칸인지 구한다.

 

[생각의 흐름]

 

1. 모든 '그 칸'에 대해서 시뮬레이션을 해보고, 결과에 따라서 정답의 카운트를 올려준다. 

현재 위치한 칸에 어떤 문자가 적혀있는지에 따라서 갈 방향이 정해져있기 때문에

내가 따로 특별한 조건이나 로직을 설정할 필요가 없다. 

즉, 요소에 움직일 수 있는 동력(?)을 불어넣고 알아서 갈 수 있는 방향으로 움직이다가

경계 밖으로 나온 것만 카운트 해준다..'칸마다 경로가 유일하므로' 큐에 넣었다가 큐에서 요소가 빠질

때 카운트가 곧 정답이다.

 

~~라고 생각하면 함정이 보인다. 요소가 큐에서 언제 빠지는가? 항상 빠질 수 있는가? 만약 맵이

RD

UL

이렇게 생겼을 때 R에서 출발하면 빙글빙글 무한루프에 빠진다. 그렇다고 visit을 체크해버리면

RDU
URU

DRL

이런 맵에서 (1,3)인 U가 먼저 큐에 들어갔다가 나와서 visit 체크를 해뒀는데 

(2,3)인 U에서 올라가지 못하게 된다.  

 

2.생각을 다르게 해봐야한다!

경로가 하나 있으면 그 안의 요소들은 한 경로에 포함이 된다는 것에 주목하자.(이 문제를 해결해야한다)

그렇다면 그 경로를 대표할만한 요소는??경로의 끝, 경계 부근에 있는 요소일 것이다.

맵의 어떤 요소이든 가장자리를 거쳐서 경계 밖으로 나갈 것이다.

그 말은 즉, 가장자리에서 출발하되 역으로 이동을 하면 해당 요소들을 모두 만날 수 있다는 뜻이다.

가장자리에 있는 요소들 중에서 바로 경계를 벗어날 수 있는 요소들만

큐에 넣고, 역방향으로 이동하며 만나는 요소들을 모두 카운트 해준다. 

 

물론 역방향으로 이동할 때엔 네방향을 모두 봐야한다.

이전 칸에서 지금의 칸으로 올 때 왼쪽으로 꺾어서 왔는지 내려왔는지 올라왔는지 모르기 때문이다. 

그렇게해서 만난 요소는 나가는 것이 가능한 칸이라고 결정이 난 것이고, 그 요소를 다시 확인할 필요는 없다.

그래서 visit으로 체크를 해준다. 

마치 동굴의 입구를 찾아서, 길을 뚫어내며 갇혀있던 사람들을 구하는 것과 같다. 이미 만난 사람은

내가 뚫어온 길로 가면 되니 해결된 사람이고, 나는어디 처박혀 있는 친구들을 더 찾으러 깊이 들어가는 셈이다.

(예전에 탈옥 문제가 생각난다..ㅎㅎ)

 

+사실, 무한루프에 빠지는 경우가 생각나지 않더라도 500x500의 맵에서 최악의 경우를 가정했을때

(1,1)에서 지그재그로 모든 요소를 거쳐서 (500,500)으로 빠져나가는 경우를 생각하면

그 사이의 요소들이 같은 경로를 통해 (500,500)으로 다시 빠져나가하므로

시간복잡도가 n^2이 되는 것을 알 수 있다. (요소가 총 25만개이므로 시간초과가 날 시간복잡도이다.)

그냥 대충 큐에 때려넣어버리면 안되는 문제!!

 

 

 

 

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>
using namespace std;
struct pos {
	int x, y;
};
int offset[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } };  //R D L U
int map[501][501];
int visit[501][501];
int main() {
	//freopen("Text.txt", "r", stdin);
	int n, m, cnt = 0;
	
	queue<pos> q;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++) {
			char ch;
			cin >> ch;
			if (ch == 'R')   //입력받을때 문자 대신 숫자로 입력
				map[i][j] = 0;
			else if (ch == 'D')
				map[i][j] = 1;
			else if (ch == 'L')
				map[i][j] = 2;
			else
				map[i][j] = 3;

			int x = i + offset[map[i][j]][0];  //바로 다음 칸이 경계를 넘는지 확인
			int y = j + offset[map[i][j]][1];
			if (x < 0 || y < 0 || x >= n || y >= m) {
				pos p;
				p.x = i;
				p.y = j;
				visit[i][j] = 1;
				q.push(p);  //뚫린 가장자리라면 큐에 넣음
				cnt++;
			}
		}

	while (!q.empty()) {   
		pos cur = q.front();
		q.pop();
		for (int d = 0; d < 4; d++) {
			int x = cur.x + offset[d][0];
			int y = cur.y + offset[d][1];
			if (x < 0 || y < 0 || x >= n || y >= m || visit[x][y] == 1)
				continue;
			if (map[x][y] == (d + 2) % 4) {  //역방향으로 나간다
				visit[x][y] = 1;
				pos pn;
				pn.x = x;
				pn.y = y;
				q.push(pn);
				cnt++;
			}
		}
	}

	cout << cnt;
	return 0;
}