백준 19238 : 스타트 택시

https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

 

최단거리 문제다. bfs로 해결 가능하다. 단, 예외처리 해야할게 꽤 있다. 골드4 티어임에도 정답률이 20% 미만이다...

예외처리는 이 글을 참고하도록 하자... https://www.acmicpc.net/board/view/57650

 

예외처리 외에도 우선순위가 행 작은순, 열 작은순인데 단순히 이동 순서로 우선순위를 맞춰주려고 하다가 계속 틀렸다. 옛날에도 이래서 오랫동안 맞왜틀 하고있었던 적이 있는 것 같은데 앞으로는 조심하도록 하자.

 

#include <iostream>
#include <queue>
#include <tuple>

#define X first
#define Y second
using namespace std;
using pii = pair<int, int>;

int n, m, fuel;
int board[21][21];
pii passenger[403];
int dx[] = { 0, -1, 0, 1 };
int dy[] = { -1, 0, 1, 0 };

// flag == 0 -> 가까운 승객 찾기
// flag == 1 -> 목적지까지 이동하기
pair<int,int> bfs(int sx, int sy, bool flag) {
	// 이미 승객의 위치에 있는 경우
	if (!flag && board[sy][sx] > 1) return make_pair(sx, sy);

	// 공통 지역 변수
	int curx, cury, cur_cost, nx, ny;
	queue<tuple<int, int, int>> q;
	bool visited[21][21] = { 0, };
	bool found = 0;

	// flag == 0일 때 사용하는 지역 변수
	int passx = 0, passy = 0, min_cost = 0;
	// flag == 1일 때 사용하는 지역 변수
	int cur_p = board[sy][sx];
	
	// 현재 승객을 태우고 board를 비워줌
	board[sy][sx] = 0;
	q.emplace(sx, sy, 0);
	visited[sy][sx] = 1;

	while (!q.empty()) {
		tie(curx, cury, cur_cost) = q.front();
		q.pop();

		// flag == 0이고 승객의 위치에 도착한 경우
		if (!flag && board[cury][curx] > 1) { 
			// 찾았음을 표시
			found = 1;
			// min_cost 값을 저장하고 cur_cost == min_cost인 동안만 q를 확인
			if (!min_cost || cur_cost == min_cost) {
				min_cost = cur_cost;
				// 승객을 처음 발견한 경우, 승객 좌표 저장
				if (!passx) passx = curx, passy = cury;
				else {
					// 이전에 저장된 승객과 행, 열 좌표 비교하여 우선순위대로 갱신
					if (passy > cury) passx = curx, passy = cury;
					else if (passy == cury && passx > curx) passx = curx;
				}
				continue;
			}
			else break;
		}
		// flag == 1이고 현재 택시에 탑승한 승객의 목적지에 도착한 경우
		else if (flag && curx == passenger[cur_p].X && cury == passenger[cur_p].Y) { found = 1; break; }

		for (int i = 0; i < 4; i++) {
			nx = curx + dx[i], ny = cury + dy[i];
			if (nx <= 0 || ny <= 0 || nx > n || ny > n || visited[ny][nx] || board[ny][nx] == 1) continue;
			visited[ny][nx] = 1;
			q.emplace(nx, ny, cur_cost + 1);
		}
	}

	// flag == 0일 경우 min_cost를, 아닐 경우 cur_cost를 빼줌
	if (!flag) fuel -= min_cost;
	else fuel -= cur_cost;

	// 현재 연료로 이동하지 못하는 곳이거나 길이 막혀서 이동하지 못했을 경우
	if (fuel < 0 || !found) return make_pair(-1, -1);
	// 목적지에 도착한 경우, 이동한 거리 * 2만큼 연료 보충
	if (flag) fuel += cur_cost * 2;

	// flag == 0일 때, 승객 좌표, 아닐 경우 현재 좌표 리턴
	if (!flag) return make_pair(passx, passy);
	else return make_pair(curx, cury);
}

void solution() {
	int sx, sy;
	int fx, fy, tx, ty;
	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;
	for (int i = 2 ; i <= m + 1; i++) {
		cin >> fy >> fx >> ty >> tx;
		// 승객의 위치는 board에, 목적지는 별도의 배열에 삽입
		// 승객의 위치를 int값으로 주기 위하여 이미 board에서 사용되고 있는 0, 1을 제외한 2부터 시작
		board[fy][fx] = i, passenger[i] = make_pair(tx, ty);
	}

	pair<int, int> cur_pos = make_pair(sx, sy);
	while (m--) {
		// 가장 가까운 승객 찾기
		cur_pos = bfs(cur_pos.X, cur_pos.Y, 0);
		// 승객을 찾지 못한 경우 예외처리
		if (cur_pos.X < 0) { cout << -1 << '\n'; return; }

		// 승객 목적지까지 이동
		cur_pos = bfs(cur_pos.X, cur_pos.Y, 1);
		// 목적지에 도달하지 못한 경우 예외처리
		if (cur_pos.X < 0) { cout << -1 << '\n'; return; }
	}

	cout << fuel << '\n';
}

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

	return 0;
}

메모리: 2028 kb

시간: 0 ms