백준 19238 [C++]

www.acmicpc.net/problem/19238

19238번: 스타트 택시

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;
}