💡 너비 우선 탐색/그래프 이론/그래프 탐색/구현/시뮬레이션
Memory 2032KB Time 4ms Code Length 5176B
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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
// 1. 제일 가까운 승객을 찾아서 이동한다.(BFS => 손님 위치 반환, 택시 위치 이동, 연료 소비(연료 바닥 났으면 종료))
// 기름통 확인
// 2. 승객의 목적지 까지 이동(BFS=> 도착했으면 연료 충전.(가는 도중 연료 바닥 났으면 종료)),
// 기름통확인
// 연료 충전
// 입력 : 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000)
// 입력 : 맵 (0은 빈칸, 1은 벽)
// 입력 : 운전 시작하는 칸 (y,x)
// 입력 : 각 승객의
// 1. vector 돌면서 찾으면 시간초과 될거같은데..
// 2. 맵을 만들어 위 왼 오 아래 - 순으로 bfs 찾기 하면 될라나?
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
int N, M, oil;
int wall_map[20][20];
struct loc {
int y, x;
};
struct info_queue {
int y, x, cnt;
};
struct info_vector {
int y, x, idx;
};
struct info {
loc start, goal;
bool finished;
};
bool cmp(info_vector first, info_vector second) {
if (first.y < second.y) {
return true;
}
else if (first.y == second.y) {
if (first.x < second.x) {
return true;
}
}
return false;
}
loc taxi;
vector<info> vc;
void init() {
cin >> N >> M >> oil;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> wall_map[i][j];
}
}
cin >> taxi.y >> taxi.x;
taxi.y--; taxi.x--;
for (int i = 0; i < M; i++) {
int py, px, gy, gx;
cin >> py >> px >> gy >> gx;
py--; px--; gy--; gx--;
vc.push_back({ py,px,gy,gx, false });
}
}
int dy[] = { -1,0,1,0 }; // 위 왼 아래 오
int dx[] = { 0,-1,0,1 };
int check_vc(info_queue now) {
info_queue nnow = now;
for (int i = 0; i < vc.size(); i++) {
if (vc[i].finished == true) continue; // 이미 태웠던 승객은 태우지 않음
if (vc[i].start.y == nnow.y && vc[i].start.x == nnow.x) { // 현재 위치가 vc에 있는 놈이라면
return i;
}
}
return -1;
}
int findman() {
int min_dis = 1e9;
loc nowtaxi = taxi;
queue<info_queue> q;
vector<info_vector> idx_vc;
q.push({nowtaxi.y,nowtaxi.x, 0});
int visited[20][20] = {0};
bool Flag = true;
while (!q.empty()) {
info_queue now = q.front(); q.pop();
int idx = check_vc(now);
if (idx != -1) { // 존재하는 놈이라면 최소 거리찾았다는 것.
if (Flag) {
Flag = false;
min_dis = now.cnt; // 한번에 한해서 최소 거리 갱신
idx_vc.push_back({ now.y, now.x, idx });
continue;
}
if (min_dis == now.cnt) { // 최소 거리와 같은 거리 값을 가지고 있다면
idx_vc.push_back({ now.y, now.x, idx });
continue;
}
}
if (min_dis < now.cnt) break; // 거리 최솟값보다 더 먼 거리면 안봄.
for (int i = 0; i < 4; i++) {
int ny = now.y + dy[i];
int nx = now.x + dx[i];
if (ny >= N || nx >= N || ny < 0 || nx < 0) continue;
if (wall_map[ny][nx] == 1) continue;
if (visited[ny][nx] == 1) continue;
visited[ny][nx] = 1;
q.push({ ny,nx,now.cnt + 1 });
}
}
if (idx_vc.size() == 0) return -1;
sort(idx_vc.begin(), idx_vc.end(), cmp); // 행이 가장 작고 열이 가장 작은 idx 구해냄
int index = idx_vc[0].idx;
taxi.y = vc[index].start.y; // 택시 위치 갱신
taxi.x = vc[index].start.x; // 택시 위치 갱신
oil = oil - min_dis; // 기름 최신화
vc[index].finished = true;
return index;
}
int movetogoal(int idx) {
loc start = vc[idx].start;
loc goal = vc[idx].goal;
queue<info_queue> q;
q.push({ start.y, start.x, oil });
int visited[20][20] = { 0 };
int spend_oil = 0;
while (!q.empty()) {
info_queue now = q.front(); q.pop();
if (now.y == goal.y && now.x == goal.x) { // 목적지 도달시
taxi.y = now.y; // 택시 위치 갱신
taxi.x = now.x; // 택시 위치 갱신
spend_oil = oil - now.cnt; // 사용한 기름
oil = now.cnt; // 기름 최신화
return spend_oil;
}
for (int i = 0; i < 4; i++) {
int ny = now.y + dy[i];
int nx = now.x + dx[i];
if (ny >= N || nx >= N || ny < 0 || nx < 0) continue;
if (wall_map[ny][nx] == 1) continue;
if (visited[ny][nx] == 1) continue;
visited[ny][nx] = 1;
q.push({ ny,nx,now.cnt - 1 });
}
}
return -1; // 못가는 거라면
}
int main() {
init();
// 승객 정보
for (int i = 0; i < M; i++) {
//cout << i + 1 << endl;
// 1. 제일 가까운 승객을 찾아서 이동한다.(BFS => 손님 위치 반환, 택시 위치 이동, 연료 소비(연료 바닥 났으면 종료))
int idx = findman(); // vector의 idx 반환
//cout << vc[idx].start.y << vc[idx].start.x << endl;
//cout << "oil : " <<oil << endl;
if (oil<=0 || idx == -1) { // 태우러 가는 도중에 바닥났다면 종료
oil = -1;
break;
}
// 2. 승객의 목적지 까지 이동(BFS=> 도착했으면 연료 충전.(가는 도중 연료 바닥 났으면 종료)),
int spend_oil = movetogoal(idx);
//cout << "oil : " << oil << endl;
if (oil<0 || spend_oil == -1) { // oil이 0인경우는 다시 채워지므로 종료 x
oil = -1;
break;
}
// 기름 충전
oil = oil + spend_oil * 2;
//cout << "oil : " << oil << endl;
}
cout << oil << endl;
return 0;
}
이 코드는 택시가 승객을 태우고 목적지로 이동하는 과정을 시뮬레이션하는 프로그램이다.
우선 초기 설정을 받아오고, 승객의 출발지와 목적지 정보를 저장한다.
findman 함수를 통해 택시가 가장 가까운 승객을 찾아 출발지까지 이동하고, 연료를 소비한다. 만약 연료가 바닥나면 종료된다.
movetogoal 함수를 통해 승객의 목적지까지 이동하고, 연료를 소비한다. 목적지에 도착하면 연료를 충전하고 소비한 연료의 두 배를 다시 충전한다.
모든 승객에 대해 위 과정을 반복하고, 최종적으로 남은 연료의 양을 출력한다.
이 프로그램은 BFS 알고리즘을 사용하여 택시의 위치와 승객의 위치를 이동하며 연료를 소비하고 충전하는 과정을 반복한다.
