BOJ : 19238 스타트 택시

---

[BOJ 19238(G4) 리뷰]

시뮬레이션 + BFS문제다. 푸는데는 1시간 15분정도 걸린거 같다. 중간에 디버깅 하느라 시간을 좀 썼다.

정답비율이 낮길래 굉장히 어려운 문제일것이라 생각했는데 어렵다기 보단 구현을 하면서 여러가지 예외들을 신경 써야 한다.

우선 코딩을 하기전에 어떻게 구현을 해야할지 간략하게 정리를 하고 시작했다.

1.승객 탐색 ( BFS ) 
2.거리,행,열 순으로 정렬 (가장 가까운 승객찾기)
3.가장 가까운 승객으로 이동. (연로 가능한지 계산)
4.목적지까지 거리계산 (BFS) 
+탐색중에 연료를 넘을경우 중단 (시간절약)
5.이동 가능하면 이동

이 정도로 정리를 하고 코딩을 들어갔다.

BFS를 하나만 구현해서 하려고 했는데 약간 로직이 달라 승객을 찾는 BFS와 목적지까지 거리를 찾는 BFS를 각각 구현했다. 승객을 찾는 BFS에선 승객을 만날때마다 벡터에 넣어 모든 탐색이 끝나고 벡터를 정렬하여 가장 가까운 승객을 찾았고, 목적지까지 거리를 찾는 BFS는 BFS를 수행하다 목적지 좌표에 도달하면 거리를 반환하도록 했다.

그러나 내가 처음에 고려하지 못한점은 "모든 승객의 출발점은 다르지만 목적지는 같을 수 있다." 라는 점이였다. 그렇기에 목적지가 오버라이딩 되는 경우가 생겨 오답처리가 되었고, 목적지 처리하는것을 벡터로 구현해 목적지가 같더라도 문제가 없도록 구현을 한 후에 정답처리가 되었다.

코드가 깔끔하지는 않지만 리팩토링은 미래의 나에게 맡기겠다 ...

/*
	21.01.08
	BOJ : 19238 스타트 택시 (https://www.acmicpc.net/problem/19238)
	구현,시뮬레이션,BFS
*/
#include <bits/stdc++.h>
using namespace std;


typedef struct taxi {
	int x;
	int y;
}taxi;

typedef struct person {
	int dist;
	int x;
	int y;
}person;

int board[22][22]; //지도 (승객)

int fuel; //연료
int dist[22][22]; //방문확인
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

taxi T;
int N, M;
vector <person> info;
vector <pair<int, int>> dest;

bool cmp(person a,person b) {
	if (a.dist == b.dist) {
		if (a.x == b.x) {
			return a.y < b.y;
		}
		else
			return a.x < b.x;
	}
	else
		return a.dist < b.dist;
}

void BFS() {
	info.clear();

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			dist[i][j] = -1;
		}
	}

	queue <pair<int, int>> Q;
	Q.push({ T.x,T.y });
	dist[T.x][T.y] = 0;

	while (!Q.empty()) {
		auto cur = Q.front(); Q.pop();

		if (board[cur.first][cur.second] > 0) { //승객 찾음
			int d = dist[cur.first][cur.second];
			info.push_back({d,cur.first,cur.second});
		}

		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (nx <1 || ny<1 || nx>N || ny>N) continue;
			if (board[nx][ny] == -1 || dist[nx][ny] != -1) continue;
			dist[nx][ny] = dist[cur.first][cur.second] + 1;
			if (dist[nx][ny] > fuel) continue;
			Q.push({ nx,ny });
		}
	}
}

int Find(int num) {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			dist[i][j] = -1;
		}
	}

	queue <pair<int, int>> Q;
	Q.push({ T.x,T.y });
	dist[T.x][T.y] = 0;

	while (!Q.empty()) {
		auto cur = Q.front(); Q.pop();

		if (dest[num].first ==cur.first && dest[num].second == cur.second) { //목적지 찾음
			T.x = cur.first;
			T.y = cur.second;
			return dist[cur.first][cur.second];
		}

		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (nx <1 || ny<1 || nx>N || ny>N) continue;
			if (board[nx][ny] == -1 || dist[nx][ny] != -1) continue;
			dist[nx][ny] = dist[cur.first][cur.second] + 1;
			if (dist[nx][ny] > fuel) continue;
			Q.push({ nx,ny });
		}
	}

	return -1;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> N >> M >> fuel;
	dest.push_back({ 0,0 });
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> board[i][j];
			if (board[i][j] == 1) //벽 -1로
				board[i][j] = -1; 
		}
	}

	cin >> T.x >> T.y;

	
	for (int i = 1; i <= M; i++) {
		int fromX, fromY, toX, toY;
		cin >> fromX >> fromY >> toX >> toY;

		board[fromX][fromY] = i;
		dest.push_back({ toX,toY });
	}
	int cnt = 0;

	while (true) {
		if (cnt == M) {
			break;
		}
		//가장 가까운 승객 찾기
		BFS();
		sort(info.begin(), info.end(), cmp);
		if (info.size() == 0) { //태울 수 있는 승객 없음
			cout << -1;
			return 0;
		}

		int nx = info[0].x;
		int ny = info[0].y;
		int d = info[0].dist;
		int num = board[nx][ny];

		//승객 지우기
		board[nx][ny] = 0;

		if (d > fuel) { //이동 불가
			cout << -1;
			return 0;
		}

		//승객위치 까지 이동하기
		T.x = nx;
		T.y = ny;
		fuel = fuel - d;

		//목적지까지 거리 찾기
		int destDist = Find(num);

		//이동하기
		if (destDist == -1 || destDist > fuel) {
			cout << -1;
			return 0;
		}
		fuel = fuel - destDist;

		//연료채우기
		fuel = fuel + destDist * 2;
		cnt++;
	}

	cout << fuel;
	return 0;
}