문제 URL : https://www.acmicpc.net/problem/19238
19238번: 스타트 택시
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다
www.acmicpc.net
문제접근법 : 문제는 쉬운데 말장난 때문에 여러번 틀렸네요 여러번 코드를 다시짜봐도 논리적인 동작원리는 똑같고 무엇이 틀렸는지 감이 안잡히고 질문글들을 읽었습니다. 덕분에 알아 냈는데
모든 출발지는 서로 다르며 , 각 손님의 출발지와 목적지는 다르다.
이말이 모든 출발지는 서로 다르다는건 쉽게 이해할수있는데 , 각손님의 출발지와 목적지가 다르다 라는게 각 손님들의 목적지가 당연히 전부 다른줄 알았습니다. ㅠ.ㅠ 제가 국어를 못해서...
즉 출발지는 다르지만 목적지는 같을수 있다라는 뜻이더군요
1번이라는 사람이 신도림에서 출발해서 목적지가 홍대입구역으로 가야하고
2번이라는 사람이 신촌에서 출발해서 목적지가 홍대입구역으로 가야하는것처럼
1,2번의 출발지는 무조건 달라야하지만 목적지가 같을수 있는것을 판단해줘야합니다.
어떤 자료구조를 사용하든 상관없기에 저는 vector를 이용했습니다.
논리적인 동작원리는 이렇게 동작합니다.
1번 : 승객을 찾아본다 bfs로 탐색 찾으면 가장가까운거리에 있는것들 중 y,x좌표 순으로 정렬 tuple이용하는게 빠름
만약 찾지못하면 프로그램 종료 -1 (벽때문에 못찾을수도있음)
2번 : 찾았다면 현재 가지고있는 연료에서 거리만큼 연료를 줄여주고 연료가 음수라면 프로그램종료시킴
(가지고 있는 연료로는 어떤승객도 찾을수 없다는뜻임)
3번 : 승객을 찾았으니 내위치를 승객의 위치로 셋팅해주고 목적지까지 바래다줌 이것도 bfs이고 동작원리는 1,2번과 똑같음
4번 : 현재연료에서 거리의 차이가 음수라면 프로그램 종료 시키고 아니라면 반대로 더해주면됨
5번: 이것을 1~4번을 m번 반복하면됨
소스코드 :
|
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
|
//By 콩순이냉장고
#include <bits/stdc++.h>
using namespace std;
int n, m, fuel;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
int board[21][21];
int passengers[21][21];
//도착지점은 같을수 있음
vector<pair<int, int>> destination;
int sy, sx;
void input() {
cin >> n >> m >> fuel;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> board[i][j];
}
}
cin >> sy >> sx;
destination.resize(m + 1);
for (int i = 1; i <= m; i++) {
int y1, x1, y2, x2;
cin >> y1 >> x1 >> y2 >> x2;
passengers[y1][x1] = i;
destination[i] = { y2,x2 };
}
}
bool isrange(int y, int x) {
return 1 <= y && y <= n && 1 <= x && x <= n;
}
bool findbfs(int& distance, int& idx, int& cy, int& cx) {
queue<pair<int, int>> q;
q.push({ sy,sx });
int length = 0;
bool visit[21][21] = { 0 };
vector<tuple<int, int, int>> v;//y,x좌표순으로 정렬하고 3번째는 승객의 번호
while (!q.empty()) {
int qsize = q.size();
while (qsize--) {
int y = q.front().first;
int x = q.front().second;
q.pop();
//승객이있는지 택시가 움직이지 않고도 그자리에 승객이 있을수도있음
if (passengers[y][x]) {
v.push_back({ y,x,passengers[y][x] });
}
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(ny, nx) && !board[ny][nx] && !visit[ny][nx]) {
q.push({ ny,nx });
visit[ny][nx] = 1;
}
}
}
if (!v.empty()) {
sort(v.begin(), v.end());
distance = length;
tie(cy, cx, idx) = v[0];
return true;
}
length++;
}
return false;
}
bool gobfs(int& distance, int idx, int& cy, int& cx) {
queue<pair<int, int>> q;
q.push({ sy,sx });
int length = 0;
bool visit[21][21] = { 0 };
while (!q.empty()) {
int qsize = q.size();
while (qsize--) {
int y = q.front().first;
int x = q.front().second;
q.pop();
if (destination[idx].first==y&&destination[idx].second==x) {
distance = length;
cy = y;
cx = x;
return true;
}
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(ny, nx) && !board[ny][nx] && !visit[ny][nx]) {
q.push({ ny,nx });
visit[ny][nx] = 1;
}
}
}
length++;
}
return false;
}
void solve() {
for (int i = 1; i <= m; i++) {
int distance = 0, cy = 0, cx = 0, idx = 0;
if (!findbfs(distance, idx, cy, cx)) {//승객찾기
fuel = -1;
break;
}
//거리만큼 빼줌
fuel -= distance;
//위치 셋팅
sy = cy;
sx = cx;
passengers[sy][sx] = 0;//승객을 태움
if (fuel < 0)break;//연료부족한지
if (!gobfs(distance, idx, cy, cx)) {//목적지까지 출발
fuel = -1;
break;
}
if (fuel - distance < 0) {
fuel = -1;
break;
}
fuel += distance;
sy = cy;
sx = cx;
}
cout << (fuel < 0 ? -1 : fuel) << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 1043 거짓말 (0) | 2021.08.15 |
|---|---|
| 백준 20058 마법사 상어와 파이어스톰 (0) | 2021.08.13 |
| 백준 1948 임계경로 (0) | 2021.08.04 |
| 백준 3111 검열 (0) | 2021.08.04 |
| 백준 1865 웜홀 (0) | 2021.07.26 |
