[ BOJ / C++ ] 2310번 : 어드벤처 게임

[ BOJ ] 2310번 : 어드벤처 게임

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

---

[  문제  ]

어드벤처 게임을 하던 중, 1부터 n까지의 번호가 붙은 방을 지나가야 하는 마법의 미로를 마주쳤다. 각 방 안에는 번호가 붙은 문이 있을 수 있고, 각 문은 해당하는 번호의 방으로 통한다. 방 안에는 레프리콘이나 트롤이 있을 수도 있다.

레프리콘이 있는 방에 들어가면 레프리콘은 모험가의 소지금이 일정 양 이하로 떨어지지 않게 채워준다. 레프리콘은 모험가의 소지금이 일정량 미만일 때에는 그만한 양이 되도록 금화를 채워주고, 소지금이 일정량 이상일 때에는 그대로 둔다. 트롤이 있는 방에 들어가려면 일정량의 통행료를 지불해야 한다. 이는 맨 처음에 모험가가 1번 방에서 시작하려 할 때에도 마찬가지이다.

모험가는 소지금이 0인 상태에서 출발한다. 과연 모험가는 1번 방에서 출발해서 n번 방에 도착할 수 있을까?

[  입력  ]

입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타내는 알파벳 하나(E: 빈 방, L: 레프리콘, T: 트롤)와 그 방의 레프리콘이나 트롤이 정해놓은 금액(빈 방일 경우 0이고, 금액은 500보다 작거나 같은 자연수), 그리고 그 방에서 다른 방으로 갈 수 있는 문의 번호들로 이루어진다. 각 줄은 0으로 끝난다. 미로의 방 수가 0개인 입력이 들어오면 입력을 종료한다.

[  출력  ]

출력은 각 미로마다 한 줄씩으로 이루어진다. 각 줄에는 1번 방에서 n번 방까지 갈 수 있는지를 "Yes" 또는 "No"로 출력한다.

---

[  문제 접근 및 풀이  ]

입력이 여러 개의 미로기 때문에 2차원 vector는 지역 변수로 사용해

따로 초기화 시키지 않았다.

1번 방에서 출발해서 n번 방까지 가는 것이 목표지만

1번방을 들어가는 것에서 트롤이 있는 방이 걸린다면 들어가지 못하기에 첫 1번 방에 들어갈 때 

확인 후 queue에 넣어주었다.

방의 값을 확인하기 위해서 pair 배열을 사용했고,

queue에서 현재 있는 방에서 다음 방에 넘어갈 때

트롤과 레프리콘 확인 및 조건을 넣고 재방문을 할 수도 있기에

돈이 더 많이 들고 있는 상태에서는 재방문을 허용 시켰다.

[  소스 코드  ]

#include<bits/stdc++.h>
using namespace std;
int N;
int vis[1001];
pair<char,int> Room_infor[1001];
void Q_15662();
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	while(true){
	    cin >> N;
	    if(!N) return 0;
	    Q_15662();
	}
}
void Q_15662(){
    
    vector<int> V[1001];
    for(int i=1;i<=N;i++){
        vis[i]=0;
        Room_infor[i]={0,0};
        char cate;
        int amount,room;
        cin >> cate >> amount;
        Room_infor[i]={cate,amount};
        while(true){
            cin >> room;
            if(!room) break;
            V[i].push_back(room);
        }
    }
    int Money=0;
    if(Room_infor[1].first=='T' && Room_infor[1].second>0) {
        cout <<"No\n";
        return;
    }
    else if(Room_infor[1].first=='L' && Money<Room_infor[1].second) Money=Room_infor[1].second;
    queue<pair<int,int>> q;
    q.push({1,Money});
    vis[1]=Money;
    while(!q.empty()){ //돈을 많이 든 상태로 들어간 거는 방문, 적게 들어간 건 continue
        auto cur=q.front(); q.pop();
        for(auto x:V[cur.first]){
            int M= cur.second;
            if(Room_infor[x].first=='T'){
                if(Room_infor[x].second>cur.second) continue;
                M-=Room_infor[x].second;
            }
            else if(Room_infor[x].first=='L'){
                if(M<Room_infor[x].second) M=Room_infor[x].second;
            }
            if(vis[x]!=0 &&vis[x]>=M) continue;
            if(x==N){
                cout <<"Yes\n";
                return;
            }
            vis[x]=M;
            q.push({x,M});
        }
    }
    cout <<"No\n";
}

---