[백준 2310 - C++] 어드벤처 게임

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

2310번: 어드벤처 게임

문제

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

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

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

입력

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

출력

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

 

풀이

 

이 문제는 원래는 java를 써서 풀려고 했습니다. 근데 50퍼 쯤에서 발생하는 시간초과가 고쳐지질 않더라구요...

그래서 결국 C++로 노선을 변경해서 푸니 바로 맞았습니다. 같은 알고리즘을 사용했는데 도대체 무슨 차이인지... 이해할 수가 없네요 (혹시 아시는 분은 댓글 부탁드립니다...)

 

우선 저는 각방의 정보인 E, L, T를 따로 저장해서 사용하기가 귀찮아서 T의 경우엔 cost가 음수의 값을 갖도록 넣어주었습니다.

그리고 방에 대한 정보들을 모두 저장한 후 dfs를 수행하면서 n에 도달하는지 확인합니다.

 

시간이 나면 java로 다시 풀어볼 생각입니다.

 

#include <cstdio>
#include <vector>

using namespace std;

int n;
vector<vector<int>> way;
int cost[1001];
int visited[1001];
int sw;

void dfs(int now, int money){
    if(sw == 1)
        return;
    
    // n번째 방 도착
    if(now == n) {
        sw = 1;
        return;
    }
    
    for(int i=0; i<way[now].size(); i++) {
        int next = way[now][i];
        
        if(visited[next] == 1)
            continue;
        
        // L
        if(cost[next] > 0 ) {
            if(cost[next] > money)
                money = cost[next];
        }
        // T or E
        else
            money += cost[next];
        
        //돈 부족해서 못감
        if(money < 0)
            return;
        
        visited[next] = 1;
        dfs(next, money);
        visited[next] = 0;
    }
}

int main () {
    
    while(1){
        scanf("%d", &n);
        if(n == 0)
            break;
       
        way.resize(n+1);
        sw = 0;
        for(int i=1; i<=n; i++){
            char info;
            int c;
            getchar();
            scanf("%c %d", &info, &c);
            while(1) {
                int next;
                scanf("%d", &next);
                if(next == 0)
                    break;
                way[i].push_back(next);
            }
            if(info == 'T')
                cost[i] = -c;
            else
                cost[i] = c;
        }
        
        if(cost[1] >= 0) {
            visited[1] = 1;
            dfs(1, cost[1]);
        }
        
        if(sw == 1)
            printf("Yes\n");
        else
            printf("No\n");
        
        way.clear();
        for(int i=0; i<=n; i++){
            cost[i] = 0;
            visited[i] = 0;
        }
        
    }
}