백준 2310번 어드벤처 게임 C++

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

 

방문표시를 어떤 금액을 가지고 어떤 방을 들어갔는지 정보를 가지고 하면 bfs로 쉽게 풀 수 있다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n;

struct RoomInfo {
    char type;
    int cost;
    vector<int> nextRooms;
};

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

    while (true) {
        cin >> n;
        if (n == 0)
            break;

        vector<vector<bool>> found(n + 1, vector<bool>(501, false));
        vector<RoomInfo> RoomInfos(n + 1);

        for (int i = 1; i <= n; i++) {
            char type;
            int cost;
            cin >> type >> cost;
            vector<int> nextRooms;
            while (true) {
                int nextRoom;
                cin >> nextRoom;
                if (nextRoom == 0)
                    break;
                nextRooms.push_back(nextRoom);
            }
            RoomInfos[i] = { type,cost,nextRooms };
        }

        queue<pair<int, int>> q;

        int startCost = 0;
        if (RoomInfos[1].type == 'L') {
            startCost = max(startCost, RoomInfos[1].cost);
        }
        if (RoomInfos[1].type == 'T') {
            startCost -= RoomInfos[1].cost;
        }

        if (startCost >= 0) {
            q.push({ 1,startCost });
            found[1][startCost] = true;
        }

        bool ans = false;

        while (!q.empty()) {
            auto curr = q.front();
            q.pop();
            if (curr.first == n) {
                ans = true;
                break;
            }
            int currCost = curr.second;
            for (auto nextRoomIdx : RoomInfos[curr.first].nextRooms) {
                int nextCost = currCost;
                if (RoomInfos[nextRoomIdx].type == 'L') {
                    nextCost = max(nextCost, RoomInfos[nextRoomIdx].cost);
                }
                else if (RoomInfos[nextRoomIdx].type == 'T') {
                    nextCost -= RoomInfos[nextRoomIdx].cost;
                }
                if (nextCost < 0) continue;
                if (found[nextRoomIdx][nextCost]) continue;

                q.push({ nextRoomIdx,nextCost });
                found[nextRoomIdx][nextCost] = true;
            }
        }
        if (ans)
            cout << "Yes";
        else
            cout << "No";
        cout << "\n";
    }
}