boj 2310 어드벤처 게임

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

 

이 문제에서 고려할 부분은 cost를 적절하게 소모하여 1번 방에서 N번 방까지 이동시켜야 합니다.

각 방마다 type이 3개가 있기 때문에 어떤 방에서 cost가 소모되는지, 추가되는지, 유지되는지를 확인해야 합니다.

 

type == E이면 빈 방이며, cost가 들지 않습니다.

type == L이면 레프리콘 방으로, 현재 cost, 이동할 방의 cost 중 높은 값을 갖게 됩니다.

type == T이면 트롤 방으로, 해당 방의 cost만큼 소모해야 합니다. 더 적은 금액을 갖고있다면 지나갈 수 없습니다.

여기서 E 방은 cost가 0인 L방으로 취급이 가능합니다.

따라서 저는 L, T 2가지 경우만 고려했습니다.

 

전체적인 로직으로는 1번 방부터 출발하여 연결되어 있는 모든 방을 bfs로 탐색합니다.

나머지는 위에 작성한 것들을 참고하여 다음 방으로 이동하면 됩니다.

cost마다 어떤 방을 갈 수 있거나 못 가는 경우가 나뉘기 때문에 visit 배열을 2차원 배열로 사용하여 방문처리를 다르게 했습니다.

 

"이는 맨 처음에 모험가가 1번 방에서 시작하려 할 때에도 마찬가지이다."

라는 말이 문제에 명시되어 있어서 1번 방부터 cost를 검사해야 합니다.

1번 방에서는 금액이 0이기 때문에 T번 방이고 cost가 있다면 false를 리턴해주도록 하고,

나머지의 경우에는 해당 방의 cost만큼의 금액을 더하여 출발해주시면 되겠습니다.

 

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#define MAX_N 1001
#define MAX_COST 501
using namespace std;
typedef pair<int, int> pii;
 
typedef struct Node {
    char type;
    int cost;
    vector<int> next;
}Node;
 
Node list[MAX_N];
bool visit[MAX_N][MAX_COST];
int N;
 
bool bfs(int s) {
    queue<pii> q;
    if (list[s].type == 'T' && list[s].cost) return false;
    else {
        q.push({ s,list[s].cost });
        visit[s][list[s].cost] = true;
    }
 
    while (!q.empty()) {
        int x = q.front().first;
        int cost = q.front().second;
        q.pop();
 
        if (x == N) return true;
 
        for (auto next : list[x].next) {
            if (list[next].type == 'T') {
                if (cost < list[next].cost) continue;
                if (visit[next][cost - list[next].cost]) continue;
                q.push({ next, cost - list[next].cost });
                visit[next][cost - list[next].cost] = true;
            }
            else {
                if (visit[next][max(cost, list[next].cost)]) continue;
                q.push({ next, max(cost, list[next].cost) });
                visit[next][max(cost, list[next].cost)] = true;
            }
        }
    }
 
    return false;
}
 
void func() {
    if (bfs(1)) cout << "Yes\n";
    else cout << "No\n";
}
 
void input() {
    cin >> N;
    if (!N) exit(0);
 
    int x;
    for (int i = 1; i <= N; i++) {
        cin >> list[i].type >> list[i].cost;
        while (1) {
            cin >> x;
            if (!x) break;
            list[i].next.push_back(x);
        }
    }
}
 
void init() {
    memset(visit, false, sizeof(visit));
    for (int i = 1; i <= N; i++) {
        list[i].next.clear();
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    while (1) {
        input();
        func();
        init();
    }
 
    return 0;
}