반응형

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

 

2310번: 어드벤처 게임

입력은 여러 개의 미로로 주어진다. 각 미로의 첫 줄에는 미로의 방 수를 나타내는 정수 n(1 ≤ n ≤ 1000)이 주어진다. 다음 n 줄에는 각 방의 정보가 주어진다. 각 방의 정보는 방의 내용물을 나타

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited[ n ][ 501 ] 배열을 만들어 얼마의 소지금을 들고 해당 노드를 방문했는지 기록합니다.

 

2. vector<int> list[1001]을 이용하여 해당 노드에서 갈 수 있는 노드들을 저장합니다.

 

3. bfs를 활용하여 queue에 넣어가면서 방을 이동하고, n번 방에 도착할 수 있으면 Yes를 출력하고, 그렇지 않으면 No를 출력합니다.

 

[ 소스코드 ]

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<iostream>
#include<vector>
#include<queue>
 
using namespace std;
 
int n;
char room[1001];
int charge[1001];
vector<int> list[1001];
int visited[1001][501];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    list[0].push_back(1);
 
    while (1) {
        cin >> n;
        if (n == 0) return 0;
 
        for (int i = 1; i <= n; i++) {
            list[i].clear();
            fill(visited[i], visited[i] + 501, 0);
            cin >> room[i] >> charge[i];
            int next;
            while (1) {
                cin >> next;
                if (next == 0) break;
                list[i].push_back(next);
            }
        }
 
        queue<pair<int, int>> q;
 
        q.push({ 0, 0 });
 
        bool flag = false;
 
        while (!q.empty()) {
            const int cur = q.front().first;
            const int cost = q.front().second;
            q.pop();
 
            if (cur == n) {
                cout << "Yes\n";
                flag = true;
                break;
            }
 
            for (int& next : list[cur]) {
                if (room[next] == 'T') {
                    if (cost >= charge[next]) {
                        if (visited[next][cost] != 1) {
                            visited[next][cost] = 1;
                            q.push({ next,cost - charge[next] });
                        }
                    }
                }
                else if (room[next] == 'L') {
                    if (cost < charge[next]) {
                        if (visited[next][charge[next]] != 1) {
                            visited[next][charge[next]] = 1;
                            q.push({ next,charge[next] });
                        }
                    }
                    else {
                        if (visited[next][cost] != 1) {
                            visited[next][cost] = 1;
                            q.push({ next,cost });
                        }
                    }
                }
                else {
                    if (visited[next][cost] != 1) {
                        visited[next][cost] = 1;
                        q.push({ next,cost });
                    }
                }
            }
        }
 
        if (flag == false) {
            cout << "No\n";
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 14588번 - Line Friends (Small) (C++)  (0) 2023.05.17
[ 백준 ] 9879번 - Cross Country Skiing (C++)  (0) 2023.05.16
[ 백준 ] 1800번 - 인터넷 설치 (C++)  (0) 2023.05.14
[ 백준 ] 2820번 - 자동차 공장 (C++)  (0) 2023.05.13
[ 백준 ] 16404번 - 주식회사 승범이네 (C++)  (0) 2023.05.12

+ Recent posts

티스토리툴바