[BAE/<JOON> 문제풀이] 17090. 미로 탈출하기

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

17090번: 미로 탈출하기

서론

그래프 문제 = 티어 -3 난이도 = 실버 1문제

아이디어 직관도 쉽고 풀이도 쉽다.

---

아이디어

출발지를 미로안으로 설정해서 BFS를 하면 TLE가 날 것 같아서 경로를 역으로 설정하고 미로 외부에서 시작해서 노드 방문 여부를 체크하며 탐색했다.

---

풀이

아이디어가 전부라 진짜 쓸게 없다. 주말이니까 날먹해야지

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

struct co {
	int i, j;
};
using namespace std;
int main() {
	int n, m; cin >> n >> m; vector<vector<vector<co>>> arr(n + 2, vector<vector<co>>(m + 2)); vector<vector<int>> dp(n + 2, vector<int>(m + 2));
	for (int i = 1; i <= n; i++) {
		string t; cin >> t;
		for (int j = 1; j <= m; j++) {
			if (t[j - 1] == 'U') {
				arr[i - 1][j].push_back({ i, j });
			}
			if (t[j - 1] == 'R') {
				arr[i][j + 1].push_back({ i, j });
			}
			if (t[j - 1] == 'D') {
				arr[i + 1][j].push_back({ i, j });
			}
			if (t[j - 1] == 'L') {
				arr[i][j - 1].push_back({ i, j });
			}
		}
	}
	int sum = 0;
	for (int i = 0; i <= n + 1; i++) {
		for (int j = 0; j <= m + 1; j++) {
			if (i == 0 || j == 0 || i == n + 1 || j == m + 1) {
				queue<co> q;
				q.push({ i, j });
				while (!q.empty()) {
					co cur = q.front(); q.pop();
					for (const co& nx : arr[cur.i][cur.j]) {
						if (dp[nx.i][nx.j] == 1) {
							continue;
						}
						sum++;
						dp[nx.i][nx.j] = 1;
						q.push({ nx.i, nx.j });
					}
				}
			}
		}
	}
	cout << sum;
	return 0;
}