[C++] BOJ(백준) 2310 어드벤처 게임

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

2310번: 어드벤처 게임

 

BFS 문제다.

DFS도 가능할 것이라고 생각하나 BFS로 접근했다.

구현 요소도 포함된 것 같다.

 

재방문이 필요하다는 점에서 고민 요소가 있었다.

조건 없이 계속 재방문 하면 무한 루프가 돌거나 돌지 않아도 메모리가 터질 것이다.

무한 루프를 막기 위해 방문 시 들고 있던 돈을 기준으로 재방문 여부를 결정했다.

방에 들어와서 소지하게 된 돈이 이전에 방문했을 때의 돈을 비교해서 현재 돈이 큰 경우에만 재방문을 한다.

이 값을 방문 배열에 저장해 비교가 가능하도록 했다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n;
int visit[1001];
vector<int> v[1001];
pair<char, int> maze[1001]; 
queue<pair<int, int>> q;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	cout.tie(0);

	while (1) {
		cin >> n;
		if (n == 0) return 0;


		for (int i = 1; i <= n; i++) {
			char c;	int k;
			cin >> c >> k;
			maze[i] = { c, k };

			visit[i] = -1;
			v[i].clear();

			while (1) {
				int a;	cin >> a;
				if (a == 0) break;
				v[i].push_back(a);
			}
		}

		if (n == 1 && maze[1].first == 'T') {
			cout << "No\n";
			continue;
		}

		bool check = false;

		q.push({ 1, 0 });
		visit[1] = true;

		while (!q.empty()) {
			int coor = q.front().first;
			int coin = q.front().second;
			q.pop();

			if (coor == n) {
				check = true;
				break;
			}

			for (int i = 0; i < v[coor].size(); i++) {
				if (maze[v[coor][i]].first == 'E') {
					if (visit[v[coor][i]] < coin) {
						q.push({ v[coor][i], coin });
						visit[v[coor][i]] = coin;
					}
				}
				else if (maze[v[coor][i]].first == 'L') {
					int money = max(coin, maze[v[coor][i]].second);
					if (visit[v[coor][i]] < money) {
						q.push({ v[coor][i], money });
						visit[v[coor][i]] = money;
					}
				}
				else if (coin >= maze[v[coor][i]].second) {
					int money = coin - maze[v[coor][i]].second;
					if (visit[v[coor][i]] < money) {
						q.push({ v[coor][i], money });
						visit[v[coor][i]] = money;
					}
				}
			}

		}
		if (check) cout << "Yes\n";
		else cout << "No\n";
	}
}

Yes YES No NO 대소문자 늪에 빠졌었다...