반응형

 

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

 

19238번: 스타트 택시

첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 맵을 저장할 arr배열을 만들어 초기화합니다.

 

2. 손님의 출발지와 목적지를 start 배열과 des배열에 각각 저장합니다.

 

3. 손님의 도착 여부를 box 배열에 저장합니다.

 

4. 모든 손님들을 돌아가며 가장 가까운 손님을 찾아 이동합니다.

 

5. 손님의 목적지로 이동하고 남은 연료를 계산합니다.

 

6. 목적지로 이동할 수 없는 경우 -1을 출력합니다.

 

[ 소스코드 ]

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include<iostream>
#include<queue>
 
using namespace std;
 
int N, M, F;
int arr[21][21];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int curY, curX;
pair<int, int> start[401];
pair<int, int> des[401];
int box[401];
 
struct pos {
    int y;
    int x;
    int cnt;
};
 
int bfs(int y, int x, int desY, int desX)    //목적지 까지의 거리 return
{
    queue<pos> q;
    q.push({ y,x,0 });
    int visited[21][21] = { 0 };
    visited[y][x] = 1;
 
    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        int cnt = q.front().cnt;
        q.pop();
 
        if (y == desY && x == desX) {
            return cnt;
        }
 
        for (int i = 0; i < 4; i++) {
            int yy = y + dy[i];
            int xx = x + dx[i];
            if (yy > 0 && yy <= N && xx > 0 && xx <= N) {
                if (arr[yy][xx] != 1 && visited[yy][xx] != 1) {
                    visited[yy][xx] = 1;
                    q.push({ yy,xx,cnt + 1 });
                }
            }
        }
    }
 
    return -1;
}
 
int main()
{
    scanf("%d %d %d", &N, &M, &F);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    scanf("%d %d", &curY, &curX);
 
    for (int i = 1; i <= M; i++) {
        scanf("%d %d %d %d", &start[i].first, &start[i].second, &des[i].first, &des[i].second);
    }
 
    while (1) {
        int destination = 0;
        int min = 987654321;
        for (int i = 1; i <= M; i++) {
            if (box[i] != 1) {
                int temp = bfs(curY, curX, start[i].first, start[i].second);
                if (min > temp) {    //더 가까우면
                    min = temp;
                    destination = i;
                }
                else if (min == temp) {        //거리가 같다면
                    if (start[destination].first > start[i].first) {
                        destination = i;
                    }
                    else if (start[destination].first == start[i].first) {
                        if (start[destination].second > start[i].second) {
                            destination = i;
                        }
                    }
                }
            }
            if (min <= 0) break;
        }
 
        if (min == -1) {    //목적지로 갈 수 없다면
            printf("%d", -1);
            return 0;
        }
 
        curY = start[destination].first;
        curX = start[destination].second;
        F -= min;
        box[destination] = 1;
 
        if (F <= 0) {    //연료가 다 떨어지면
            printf("%d", -1);
            return 0;
        }
 
        int temp = bfs(curY, curX, des[destination].first, des[destination].second);
 
        if (temp == -1) {
            printf("%d", -1);
            return 0;
        }
 
        F -= temp;
 
        if (F < 0) {
            printf("%d", -1);
            return 0;
        }
 
        curY = des[destination].first;
        curX = des[destination].second;
 
        F += (temp * 2);
 
        int cnt = 0;
 
        for (int i = 1; i <= M; i++) {
            if (box[i] == 1) {
                cnt++;
            }
        }
 
        if (cnt == M) break;
    }
 
    printf("%d", F);
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 23288번 - 주사위 굴리기 2 (C++)  (0) 2022.10.03
[ 백준 ] 21609번 - 상어 중학교 (C++)  (0) 2022.10.02
[ 백준 ] 19237번 - 어른 상어 (C++)  (0) 2022.09.30
[ 백준 ] 19236번 - 청소년 상어 (C++)  (0) 2022.09.29
[ 백준 ] 20061번 - 모노미노도미노 2 (C++)  (0) 2022.09.28

+ Recent posts

티스토리툴바