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

작성일 Edited on In , Views: Disqus:

원문 링크 : https://www.acmicpc.net/problem/2310

풀이 및 구현

문제에서 주어진 방의 종류는 총 3가지이다. 간단히 정리하면 아래와 같다.

  1. 빈 방 - 아무 일도 하지 않음
  2. 레프리콘 - 소지금을 $max(소지금, 일정 금액)$으로 맞춰준다.
  3. 트롤 - 소지금이 통행료 이상 있어야 방을 진입할 수 있음

각 방는 다른 방으로 이어지는 문이 있을 수 있는데 이를 이용해 1번 방에서 시작하여 n번 방에 도착해야 하는 문제이다.

다른 방으로 이어지는 문이 있다는 부분에서 유향 그래프라는 것을 생각했고, n번 방에 도착해야 한다는 것에서 그래프 탐색 문제라는 확신이 들었다.

그래서 그래프 탐색 쪽으로 생각한 결과 너비 우선 탐색을 활용해서 현재 방 번호와 현재 소지금을 들고 탐색을 해 n번 방에 도착하는지 확인하면 된다고 생각했다.

이를 위해 우선 방의 데이터를 저장하는 구조체를 만들었다.

구조체는 방의 종류 type, 정해진 금액 cost, 연결된 다른 방의 번호 next를 저장한다.

해당 구조체를 벡터로 만들고 문제의 입력 형식에 맞게 각 방에 대한 데이터를 넣어주었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct room {
    char type; // 방의 종류
    int cost; // 레프리콘의 보정 금액 or 트롤의 통행료
    vector<int> next; // 연결된 방
};

vector<room> rooms;

int main() {

    // 생략
    
    rooms.assign(n, room());
    for (int i = 0; i < n; i++) {
        cin >> rooms[i].type >> rooms[i].cost;

        while (1) {
            int m; cin >> m;
            if (!m) break;
            rooms[i].next.push_back(m - 1);
        }
    }
     
    // 생략
      
}

코드 상에서는 1번 방을 0번 방으로, n번 방을 n-1번 방으로 계산했다.

방에 대한 정보를 저장했으면 이를 이용하여 너비 우선 탐색을 하면 된다.

{현재 방 번호, 현재 소지금}의 형태로 너비 우선 탐색을 하면서 각 방에 대해 아래와 같은 순서로 확인했다.

  1. 트롤의 방이라면 통행료를 지불할 수 있는지 확인한다.
    만약 통행료를 지불할 수 없다면 해당 방에 들어가지 않는다.
  2. 현재 방이 n번 방인지 확인한다.
    n번 방이면 이동할 수 있다고 1을 반환하며 함수를 종료한다.
  3. 재방문 여부를 확인한다.
    다시 갈 필요가 없다면 해당 방의 탐색을 종료한다.
  4. 레프리콘의 방이라면 소지금의 변화를 계산한다.
  5. 연결된 다른 방을 탐색한다.

위와 같은 순서로 탐색하면 된다.

재방문의 경우가 중요한데 문제에서 관련 제약 조건이 존재하지 않아 재방문을 할 수 있다고 생각하고 풀었다.

만약 방문한 적이 있을 때 그 당시 소지금이 현재 소지금보다 크다면 다시 갈 필요가 없지만 현재 소지금이 그 당시 소지금보다 크다면 그 당시에 가지 못했던 트롤의 방을 이번 방문을 통해 갈 수 있는 경우가 생길 수 있기 때문에 이 때에는 다시 방문을 해주어야 한다.

그래서 재방문 여부를 확인하는 벡터 vector<int> visited를 만들고 기본 값을 -1로 초기화 한다.

이후 방문을 할 때 현재 소지금과 해당 방 번호의 visited값을 확인하여 더 큰 경우만 이동할 수 있게 코드를 작성하였다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int BFS() {
    queue<array<int, 2>> q; // {현재 방번호, 현재 소지금}
    vector<int> visited(n, -1); // 재방문 여부 확인
    q.push({0, 0}); // 1번 방에서 소지금 0으로 시작
    while (!q.empty()) {
        auto [cur_room, cur_cost] = q.front();
        q.pop();

        // 현재 방이 트롤 방일 때
        if (rooms[cur_room].type == 'T') {
            // 통행료를 지불할 수 없으면 방문하지 않는다.
            if (cur_cost < rooms[cur_room].cost) continue;
            // 통행료를 지불한다.
            cur_cost -= rooms[cur_room].cost;
        }

        // 현재 방이 n번 방이면 도착할 수 있다.
        if (cur_room == n - 1) return 1;

        // 이전 방문보다 소지금이 적다면 다시 방문할 필요가 없다.
        if (cur_cost <= visited[cur_room]) continue;

        // 현재 소지금을 적는다.
        visited[cur_room] = cur_cost;

        // 레프리콘이면 소지금을 보정한다.
        if (rooms[cur_room].type == 'L') {
            cur_cost = max(cur_cost, rooms[cur_room].cost);
        }
        
        // 연결된 방을 탐색한다.
        for (int& nxt_room : rooms[cur_room].next) {
            q.push({nxt_room, cur_cost});
        }
    }
    
    // n번 방으로 이동하는 경우가 없다.
    return 0;
}

main 함수에서 BFS 함수를 호출하고 0을 반환하면 No, 1을 반환하면 Yes를 출력하면 된다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;

struct room {
    char type;
    int cost;
    vector<int> next;
};

vector<room> rooms;

int n;

int BFS() {
    queue<array<int, 2>> q;
    vector<int> visited(n, -1);
    q.push({0, 0});
    while (!q.empty()) {
        auto [cur_room, cur_cost] = q.front();
        q.pop();

        if (rooms[cur_room].type == 'T') {
            if (cur_cost < rooms[cur_room].cost) continue;
            cur_cost -= rooms[cur_room].cost;
        }

        if (cur_room == n - 1) return 1;

        if (cur_cost <= visited[cur_room]) continue;
        visited[cur_room] = cur_cost;

        if (rooms[cur_room].type == 'L') {
            cur_cost = max(cur_cost, rooms[cur_room].cost);
        }

        for (int& nxt_room : rooms[cur_room].next) {
            q.push({nxt_room, cur_cost});
        }
    }
    return 0;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    while (1) {
        cin >> n;
        if (!n) break;

        rooms.assign(n, room());
        for (int i = 0; i < n; i++) {
            cin >> rooms[i].type >> rooms[i].cost;

            while (1) {
                int m; cin >> m;
                if (!m) break;
                rooms[i].next.push_back(m - 1);
            }
        }

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

}

후기

img.png
약간의 구현을 곁들인 재미있는 그래프 탐색 문제였다.

여담으로 자유 게시판에 재방문 처리 관련 내용들이 있길래 재방문 없는 버전으로 짜려다가 현재 너비 우선 탐색으로 구현했다보니 생각보다 바꿀 부분이 많아져서 포기했다…