백준 - 스타트 택시 (19238)

1. 문제

문제 링크

2. 풀이

BFS를 이용해 곧이 곧대로 시뮬레이션 하면 풀리는 문제입니다.

전체적인 계획은 이와 같습니다.

1. BFS를 이용해 가장 가까운 승객을 찾습니다.
2. BFS를 이용해 승객의 목적지까지 이동합니다.

위 로직을 m번 반복하면 답을 얻을 수 있습니다.
물론 이동하는 도중에 연료량이 부족하면 로직을 빠져나와야 합니다.

간단한 문제이지만 놓치기 쉬운 부분이 많은 문제인데요,
저도 이 문제를 풀면서 실수했던 부분이 있어서 조금 고생했습니다.

승객들끼리 목적지가 겹치거나, 한 승객의 목적지가 다른 승객의 출발지일 수 있다.

• 저는 그림처럼 다 제각각일 줄 알고 이차원 배열에 마킹하면서 풀었는데,
  이렇게 되면 한 승객의 목적지가 출발지로 덮어씌어져서 없어져버립니다.
• 그래서 저는 passengerDest라는 이차원 배열을 선언해서 해결했습니다.

구현 문제는 정말 한 번 놓치면 시간을 많이 잡아먹는 듯 합니다.
차근차근 구현하는 습관을 계속 길러야겠습니다.

3. 전체 코드

#define SIZE 20
#define MAX SIZE * SIZE + 1
#include <bits/stdc++.h>

using namespace std;

int n, m, k, ty, tx;
int mmap[SIZE][SIZE];
int visited[SIZE][SIZE];
int passengerDest[MAX][2];
int my[4] = { -1, 0, 1, 0 };
int mx[4] = { 0, 1, 0, -1 };
queue<pair<int, int>> q, rq;

bool isOut(int y, int x) {
	return y < 0 || y >= n || x < 0 || x >= n;
}

void resetVisitied() {
	while (!q.empty()) {
		rq.push(q.front());
		q.pop();
	}

	while (!rq.empty()) {
		int y = rq.front().first;
		int x = rq.front().second;

		visited[y][x] = MAX;
		rq.pop();
	}
}

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

	cin >> n >> m >> k;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> mmap[i][j];
			visited[i][j] = MAX;
		}
	}

	cin >> ty >> tx;

	ty -= 1;
	tx -= 1;

	for (int i = 1; i <= m; i++) {
		int sy, sx, ey, ex;

		cin >> sy >> sx >> ey >> ex;

		mmap[sy - 1][sx - 1] = -i;
		passengerDest[i][0] = ey - 1;
		passengerDest[i][1] = ex - 1;
	}

	while (m--) {
		int passenger;

		// 가까운 승객에게 이동
		q.push({ ty, tx });
		visited[ty][tx] = 1;

		// 행, 열이 작은 승객을 찾기 위해 크게 초기화
		ty = n;
		tx = n;

		while (!q.empty() && k > 0) {
			int size = q.size();

			// 한 턴씩 이동
			while (size--) {
				int y = q.front().first;
				int x = q.front().second;

				rq.push(q.front());
				q.pop();

				// 승객을 찾았고 이전 승객보다 행이 작거나 행이 같아도 열이 작다면
				if (mmap[y][x] < 0 && (y < ty || y == ty && x < tx)) {
					ty = y;
					tx = x;
					continue;
				}

				for (int dir = 0; dir < 4; dir++) {
					int ny = y + my[dir];
					int nx = x + mx[dir];

					if (isOut(ny, nx)) continue;

					// 벽일 때
					if (mmap[ny][nx] == 1) continue;

					// 방문했을 때

					if (visited[ny][nx] != MAX) continue;

					q.push({ ny, nx });
					visited[ny][nx] = 1;
				}
			}

			// 승객 찾았을 때
			if (ty != n) break;

			// 연료 감소
			k--;
		}

		// 연료가 없거나 벽 때문에 승객에게 못 갈 때
		if (k <= 0 || ty == n) {
			k = -1;
			break;
		}

		passenger = -mmap[ty][tx]; // 승객 설정
		mmap[ty][tx] = 0; // 출발지 없애기

		// visited 초기화
		resetVisitied();

		// 목적지 이동
		int find = 0;
		q.push({ ty, tx });
		visited[ty][tx] = 0;
		

		while (!q.empty() && k >= 0) {
			int size = q.size();

			// 한 턴씩 이동
			while (size--) {
				int y = q.front().first;
				int x = q.front().second;

				rq.push(q.front());
				q.pop();

				// 목적지일 때
				if (y == passengerDest[passenger][0] && x == passengerDest[passenger][1]) {
					ty = y;
					tx = x;
					k += visited[y][x] * 2; // 연료 두배 충전
					find = 1;
					break;
				}

				for (int dir = 0; dir < 4; dir++) {
					int ny = y + my[dir];
					int nx = x + mx[dir];

					if (isOut(ny, nx)) continue;

					// 벽일 때
					if (mmap[ny][nx] == 1) continue;

					// 방문했을 때
					if (visited[ny][nx] != MAX) continue;

					q.push({ ny, nx });
					visited[ny][nx] = visited[y][x] + 1;
				}
			}

			if (find) break;

			// 연료 감소
			k--;
		}

		// 목적지에 못 갈 때
		if (!find) {
			k = -1;
			break;
		}

		resetVisitied();
	}

	cout << k;

	return 0;
}