Byung Wook Park (박병욱)

Byung Wook Park (박병욱)

[백준] 스타트 택시

✔️ 문제

✔️ 문제 이해

  • NxN 격자형 맵이 주어진다. 각 칸은 비어있거나(0) 벽(1)이 놓여있다.
  • 택시는 상하좌우 인접한칸으로 이동가능하고 태워야할 승객이 M명 존재한다.
  • 택시는 승객을 1명만 태울 수 있다. 따라서 승객을 태우고, 목적지로 이동하는 일을 M번 반복해야한다.
    • 승객은 움직이지 않는다. 승객은 출발지에서만 택시를 타고 목적지에서 내릴 수만 있다.
  • 택시는 승객을 태울때 현재 위치에서 최단거리가 가장 짧은 승객을 태운다.
    • 그런 승객이 여러명일 경우 행번호가 적은순, 열번호가 적은 순으로 태운다.
  • 택시는 승객을 목적지로 이동시킨다.
    • 한 칸 이동할 때마다 연료가 1 소모된다.
    • 승객을 목적지로 이동시키면 승객을 태워 이동하면서 소모한 연료량의 두 배가 충전된다.
    • 이동하는 중에 연료가 바닥나면 실패다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패가 아니다.
  • N, M, 초기 연료량 그리고 손님의 출발지 위치와 목적지 위치가 주어졌을 때 모든 손님을 이동시키고 연료를 충전했을 때 남은 연료량을 출력해야한다.
    • 연료가 바닥나서 출발지 또는 목적지로 이동 불가한 경우와 모든 손님을 이동시킬 수 없는 경우는 -1을 출력한다.

✔️ 알고리즘 설계

  • 두 개의 BFS 를 사용하여 구현한다.
    • 승객을 태우러 가는 BFS
    • 승객을 태우고 목적지로 가는 BFS
  • 알고리즘

  1. 최단거리에 있는 손님을 태운다.

    1-1. 연료가 바닥나거나 벽으로 막혀서 손님을 못태우면 -1을 출력하고 종료한다.

  2. 승객을 태웠으면 목적지로 간다.

    2-1. 연료가 바닥나거나 벽으로 막혀서 목적지로 못데려다 주면 -1을 출력하고 종료한다.

  3. 1,2를 손님 수 m 만큼 반복한다.

✔️ 상세 구현 설명

  • 위치 정보는 다음과 같이 구조체로 관리한다.
    • x좌표, y좌표, x,y 좌표까지 이동했을때 남은 연료량 f
  • 최단 거리에 있는 고객은 BFS로 찾으면 된다. BFS는 가중치가 없는 그래프에서 최단거리를 찾아준다.
    • 최단 거리가 있는 고객이 여러명이라면 vector에 모두 넣어둔다.
    • 그리고 연료량이 큰 순, 행이 적은순, 열이 적은 순으로 정렬한뒤 맨 앞 원소에 있는 고객을 태운다.
  • 승객을 태우고 목적지로 가는 것 역시 BFS로 하면 된다.
    • hash map으로 승객의 목적지 정보를 저장해두고 BFS 탐색시 매번 목적지 도달 여부를 파악한다.

👨🏻‍💻 소스 코드

#include<iostream>
#include<unordered_map>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;

typedef struct {
	int x, y, f;
}client;

int n, m, fuel, tx, ty;
int map[20][20];
int clientMap[20][20];
unordered_map<int, pair<int, int>> destInfo;
const int dx[] = {-1,1,0,0 }, dy[] = {0,0,-1,1};

// 최단거리가 같은 손님이 여러명일 경우 아래 기준으로 sort 하면된다.
bool comp(client a, client b) {
	if (a.f == b.f) {
		if (a.x == b.x) {
			return a.y < b.y; // 열번호가 적은순으로
		}
		else
			return a.x < b.x; // 행번호가 적은순으로
	}
	else
		return a.f > b.f; // 연료가 많은 순으로(거리가 가까운순으로)
}

// 손님을 목적지(=destNum)에 데려다주는 bfs 
bool goToDest(int destNum) {
	queue<client> q;
	bool check[20][20];
	int maxVal = -0x7fffffff;
	vector<client> candi;

	memset(check, 0, sizeof(check));
	q.push({ tx,ty,fuel});

	while (!q.empty()) {
		int x = q.front().x, y = q.front().y,
			f = q.front().f;
		q.pop();

		// 도착지라면
		if (destInfo[destNum].first == x 
			&& destInfo[destNum].second == y) {
			// 택시 위치, 연료 정보 업데이트
			tx = x, ty = y, fuel = f + (fuel - f) * 2; // 소모한 연료의 2배 추가.
			return true;
		}

		if (f == 0) continue; // 연료가 0일 경우

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i], ny = y + dy[i];
			int nf = f;
			if (nx >= n || nx < 0 || ny >= n || ny < 0) continue;
			if (map[nx][ny]) continue;
			if (check[nx][ny]) continue;

			nf--; // 연료 감소
			check[nx][ny] = true;
			q.push({ nx, ny, nf });
		}

	}

	return false;
}

bool rideClient(){ // 최단거리에 있는 손님들 태우러가는 bfs 함수
	queue<client> q;
	bool check[20][20];
	int maxVal = -0x7fffffff;
	vector<client> candi;

	memset(check, 0, sizeof(check));
	q.push({ tx,ty,fuel});

	while (!q.empty()) {
		int x = q.front().x, y = q.front().y,
			f = q.front().f;
		q.pop();

		if (f == 0) continue; // 연료가 0일 경우

		if (clientMap[x][y] > 0) { // 손님을 발견한 경우.
			if (f >= maxVal) { // v연료를 덜 소모해야 가까운 곳이다.
				candi.push_back({ x,y,f }); // 손님 후보군을 넣는다.
			}
			continue;
		}

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i], ny = y + dy[i];
			int nf = f;
			if (nx >= n || nx < 0 || ny >= n || ny < 0) continue;
			if (map[nx][ny]) continue;
			if (check[nx][ny]) continue;
			nf--; // 연료 감소
			check[nx][ny] = true;
			q.push({ nx,ny, nf });
		}

	}

	if (candi.size() == 0) // 손님 후보군이 없다면
		return false;

	// 정렬을 사용해 행, 열이 적은 손님을 찾는다.
	sort(candi.begin(), candi.end(), comp);

	int x = candi[0].x, y = candi[0].y, f = candi[0].f;
	int destNum = clientMap[x][y];
	clientMap[x][y] = 0; // clientMap 정보 업데이트
	tx = x, ty = y, fuel = f; // 택시 정보 업데이트

	return goToDest(destNum); // 태울 손님 번호(=목적지 번호)를 넣는다.
}

int solve(){
	for (int i = 0; i < m; i++) {
		if (!rideClient())
			return -1;
	}
	
	return fuel;
}

int main() {

	cin >> n >> m >> fuel; 

	for (int i = 0; i < n; i++) { // map 정보를 입력받는다. 
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}

	cin >> tx >> ty; // 택시 정보 입력
	tx--, ty--;

	for (int i = 1; i <= m; i++) {
		int sx, sy, ex, ey;
		cin >> sx >> sy >> ex >> ey;
		clientMap[sx - 1][sy - 1] = i; // 손님 위치 정보를 2차원 배열로 관리
		destInfo[i] = { ex - 1, ey - 1 }; // 손님의 도착지 정보를 hash map으로 관리
	}

	cout << solve();

	return 0;
}

✔️ 문제 회고

  • BFS 두 개를 사용하면 되는 문제다. 문제 조건에 따라 구현하는 시뮬레이션 문제였다.
  • 복잡할 수 있는 문제 조건을 하나하나 파악하고 깔끔하게 처리해야한다.
  • set 또는 map을 사용할때 key 값으로 구조체를 넣는 경우 구조체 우선순위 결정을 위한 비교함수를 인자로 넣어줘야한다. 우선순위 기준을 알려줘야 구조체를 set, map 내부에서 관리할 수 있다.