19238번: 스타트 택시
첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다
www.acmicpc.net
1. 풀이방법
- BFS 활용문제 입니다.
- 문제의 조건이 좀 많고 , 주의하여야할 점이 좀 있는 문제였습니다.
- 일단 저 같은 경우 승객들의 출발지점은 모두 다르므로 승객의 도착점을 찾을 때는
- 승객들 간의 분별이 가능한 출발점을 기준으로 찾았습니다 (그리고 그 찾은 승객의 INDEX를 통해서 도착점을 지정)
- 저같은 경우 첫 BFS 탐색을 통해 승객을 찾고 두번째 BFS를 통해 도착점을 찾았습니다.
- 승객을 찾아서 태우면 ground[i][j] =0 빈칸으로 바꿔주고 (한 칸에 두명 이상의 손님이 있는경우는 없으므로 상관 x)
- 도착점에 도착하면 그 도착점을 택시의 새로운 위치로 갱신하여 주었습니다.
2. 주의사항
- 도착점에서 손님을 내리고, 그곳에 손님이 있을경우 바로 태울 수 있다.
- 벽 때문에 도착하지 못하는 경우는 실패이다.
- 거리 > 행 > 열 순으로 승객을 특정한다.
- 승객을 찾으러 갈 때 연료가 부족하거나, 승객을 태우고 목적지로 가는 중 연료가 부족하면 실패이다.
- 그리고 "거리 > 행 > 열" 순으로 정렬을 하는 과정에서 실수가 있어 거의 한시간을 해맸는데..."
- 일단 2(즉, 승객) 을 찾으면 지금 현재 큐에 있는 승객들을 모두 벡터로 담아 소팅을 했는데
- 여기서 주석에서 보시다시피 while(!tmpq.empty()) 이런 실수를 했는데,
- 이럴경우 다음단계에 해당하는 녀석들도 큐에 들어가있는 상태 이므로 오류가 나옵니다.
- 보통 하나의 큐를 이용하여 bfs를 구현할 경우 한번의 반복문이 끝난후 그 큐의 size를 측정해서 하나의 단계로
- 취급하므로 이때도 while(ssize--)를 해야 했습니다.
3. 나의코드
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int ground[21][21];
bool visit[21][21];
int n, m, fuel;
int texix, texiy;
int tmpx, tmpy;
//북서동남
int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };
queue<pair<int, int>> tmpq;
bool fail = false;
int nextx, nexty;
int distances;
int ssize;
vector<pair<int,int>> tmpvector;
struct client {
int sx, sy, ex, ey;
};
vector<client> clients;
bool compare(pair<int,int> &lhs, pair<int,int> &rhs) {
if (lhs.first < rhs.first) return true;
else if (lhs.first == rhs.first) {
if (lhs.second < rhs.second) return true;
else return false;
}
else return false;
}
void inputs() {
cin >> n >> m>>fuel;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> ground[i][j];
}
}
cin >> texix >> texiy;
texix -= 1; texiy -= 1;
for (int i = 0; i < m; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
ground[x1-1][y1-1] = 2;
clients.push_back({ x1-1,y1-1,x2-1,y2-1 });
}
}
void qclear() {
while (!tmpq.empty()) {
tmpq.pop();
}
}
void visitclear() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
visit[i][j] = false;
}
}
}
bool boundcheck(int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= n) return false;
else return true;
}
void bfs() {
distances = 0;
bool checking = false;
while (1) {
if (tmpq.empty()) { fail = true; return; }
ssize = tmpq.size();
while (ssize--) {
nextx = tmpq.front().first;
nexty = tmpq.front().second;
tmpq.pop();
if (ground[nextx][nexty] == 2) { //손님을 찾으면 break;
tmpvector.clear();
tmpvector.push_back({ nextx,nexty });
while (ssize--) { // !!!!!! (!tmpq.empty()) 하면 틀림
int ttx = tmpq.front().first;
int tty = tmpq.front().second;
tmpq.pop();
if (ground[ttx][tty] == 2) {
tmpvector.push_back({ ttx,tty });
}
}
sort(tmpvector.begin(), tmpvector.end(), compare);
nextx = tmpvector[0].first;
nexty = tmpvector[0].second;
checking = true; break;
}
for (int i = 0; i < 4; i++) {
int tx = nextx + dx[i]; int ty = nexty + dy[i];
if (boundcheck(tx, ty) && visit[tx][ty] == false && ground[tx][ty] != 1) {
visit[tx][ty] = true;
tmpq.push({ tx,ty });
}
}
}
if (checking == true) { break; }
distances++;
}
fuel -= distances; //이동한만큼 연료소모
if (fuel < 0) { fail = true; return; }
ground[nextx][nexty] = 0; // 손님을 태웠슴
int clientindex = -1;
for (int i = 0; i < clients.size(); i++) {
if (clients[i].sx == nextx && clients[i].sy == nexty) {
clientindex = i; break; //손님의 목적지를 알기위해
}
}
visitclear();
qclear();
tmpq.push({ nextx,nexty }); //출발지점
ground[nextx][nexty] = 0; //손님을 태움
visit[nextx][nexty] = true;
distances = 0;
checking = false;
while (1) {
if (tmpq.empty()) { fail = true; return; }
ssize = tmpq.size();
while (ssize--) {
nextx = tmpq.front().first;
nexty = tmpq.front().second;
tmpq.pop();
if (nextx==clients[clientindex].ex &&nexty==clients[clientindex].ey) { //손님을 찾으면 break;
checking = true; break;
}
for (int i = 0; i < 4; i++) {
int tx = nextx + dx[i]; int ty = nexty + dy[i];
if (boundcheck(tx, ty) && visit[tx][ty] == false && ground[tx][ty] != 1) {
visit[tx][ty] = true;
tmpq.push({ tx,ty });
}
}
}
if (checking == true) {break; }
distances++;
}
fuel -= distances;
if (fuel < 0) {
fail = true; return;
}
texix = nextx; texiy = nexty; //택시 위치 변경
fuel += (2 * distances);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
inputs();
for (int i = 0; i < m; i++) {
qclear();
visitclear();
tmpq.push({ texix,texiy });
visit[texix][texiy] = true;
bfs();//손님찾자
if (fail == true) { cout << -1 << "\n"; return 0; }
}
cout << fuel << "\n";
return 0;
}'알고리즘 문제풀이 > DFS와 BFS' 카테고리의 다른 글
| 백준 12851 [C++] (0) | 2021.01.18 |
|---|---|
| 백준 13913 [C++] (0) | 2021.01.18 |
| 백준 17142 [C++] (0) | 2021.01.17 |
| 백준 16236 [C++] (0) | 2020.12.29 |
| 백준 2644 [C++] (0) | 2020.12.22 |
