백준 17090번 미로 탈출하기

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

17090번: 미로 탈출하기

 

 

 

 

<접근방법>

탈출은 무조건 배열 가장 바깥쪽에서 일어납니다.

그럼 역으로 따라가면 어떤 좌표들이 탈출할 수 있는지 알 수 있겠죠.

 

dp로도 풀립니다.

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <queue>
#include <memory.h>
using namespace std;

struct point {
	int y, x;
};

int n, m, res;
int map[501][501], visit[501][501];
int dy[4] = {0, -1, 0, 1};
int dx[4] = {1, 0, -1, 0};

queue<point>runner;

void bfs(int y, int x) {
	queue<point>q;
	q.push({y, x});
	visit[y][x] = 1;
	res++;

	while (!q.empty()) {
		point t = q.front();
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ty = t.y + dy[i];
			int tx = t.x + dx[i];

			if (ty < 0 || ty >= n || tx < 0 || tx >= m) continue;
			if (visit[ty][tx] == 1) continue;

			int td = map[ty][tx];

			if (td == (i + 2) % 4) {
				q.push({ty, tx});
				visit[ty][tx] = 1;
				res++;
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char c;
			cin >> c;

			if (c == 'R') {
				map[i][j] = 0;
			}
			else if (c == 'U') {
				map[i][j] = 1;
			}
			else if (c == 'L') {
				map[i][j] = 2;
			}
			else {
				map[i][j] = 3;
			}

			int ty = i + dy[map[i][j]];
			int tx = j + dx[map[i][j]];

			if (ty < 0 || tx < 0 || ty >= n || tx >= m) {
				runner.push({ i, j });
			}
		}
	}

	while (!runner.empty()) {
		point tt = runner.front();
		runner.pop();

		bfs(tt.y, tt.x);
	}

	cout << res << '\n';
	return 0;
}

 

 

---

 

 

<느낀 점>

-역으로 생각하기