[C++] 백준 19238 스타트 택시

문제 링크

---

www.acmicpc.net/problem/19238

19238번: 스타트 택시

 

접근 방법

---

문제를 해결하는 과정은 아래와 같습니다.

 

1. 현재 택시로 부터 가장 가까운 손님을 탐색하기 위해선 BFS를 사용해야 합니다. 이 때 거리가 같은 손님이 여러명 존재할 수 있기 때문에 가장 가까운 손님을 탐색완료하더라도 현재 레벨 까지는 계속해서 탐색을 해야합니다. 또한 탐색을 시작하기전 현재위치에 손님이 있는지도 먼저 검사를 해야합니다.

 

2. 손님의 위치가 탐색이 완료된다면 현재의 연료를 가지고 탐색한 위치로 이동 할 수 있는지 검사 후 이동을 합니다.

 

3. 1번 항목과 마찬가지로 BFS로 탐색을 하여 손님의 도착지 까지의 거리를 알아냅니다. 

 

4. 이후 현재의 연료를 가지고 이동 할 수 있는지 검사 후 이동을 시킵니다.  

 

5. 손님이 있던 좌표의 정보를 제거합니다.

 

6. 1번 항목부터 반복

 

자세한 사항은 소스코드에 주석을 달았습니다.

소스 코드

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>
#define MAX 10000

using namespace std;

typedef struct coord {
	int x, y;
};

typedef struct tInfo {
	coord xy;
	int cost;
};

coord direction[4] = { {1,0}, {-1,0}, {0,1}, {0,-1} };
coord passengers[21][21];
int tMap[21][21];
int N, M;

bool inRange(int x, int y) {
	return (0 <= x && x < N && 0 <= y && y < N);
}

coord comp(coord one, coord other) {
	if (one.x < other.x)
		return one;
	else if (one.x == other.x) {
		if (one.y < other.y)
			return one;
		else
			return other;
	}
	else
		return other;
}

tInfo BFS(int x, int y, int state) { 
//state == 1 -> 택시가 손님에게
//state == 2 -> 손님을 태우고 목적지로

	queue <tInfo> q;
	vector<vector<bool>> visited(N, vector<bool>(N));
	coord ret = {MAX, MAX};
	int dist = 0;

	q.push({ x,y,0 });
	visited[x][y] = true;

	if (state == 1 && passengers[x][y].x != -1 && passengers[x][y].x != -1) //현재 위치에 손님이 있다면
		return { {x,y},0 };

	while (!q.empty()) {

		bool flag = false;
		int size = q.size();

		while (--size >= 0) { // 레벨 탐색

			int now_x = q.front().xy.x;
			int now_y = q.front().xy.y;
			int cost = q.front().cost;
			q.pop();

			for (int i = 0; i < 4; i++) {

				int next_x = now_x + direction[i].x;
				int next_y = now_y + direction[i].y;

				if (inRange(next_x, next_y)) {
					if (!visited[next_x][next_y] && tMap[next_x][next_y] == 0) {

						if (state == 1) { // 손님이 있는 곳으로
							if (passengers[next_x][next_y].x != -1 && passengers[next_x][next_y].x != -1) { //손님이 있는 곳
								flag = true; //탐색을 1번이라도 성공했다는 flag
								ret = comp(ret, { next_x, next_y }); //문제의 조건에 따라 손님의 우선순위 결정
								dist = cost + 1;
							}
						}
						else { //택시가 손님을 태우고 목적지로
							if (passengers[x][y].x == next_x && passengers[x][y].y == next_y) { //목적지에 도착했을 때
								ret = { next_x, next_y };
								return { ret, cost + 1};
							}
						}
						q.push({ next_x, next_y, cost + 1 });
						visited[next_x][next_y] = true;
					}
				}
			}
		}
		if (flag)
			break;
	}

	return { ret, dist };
}

bool canGo(tInfo &taxi, tInfo to, int state) {  
//state == 1 -> 택시가 손님한테 가는 동작
//state == 2 -> 손님이 목적지에 가는 동작 
	if (to.xy.x == MAX && to.xy.x == MAX)
		return false;
	if (taxi.cost - to.cost >= 0) {
		taxi.xy.x = to.xy.x;
		taxi.xy.y = to.xy.y;

		if (state == 1) // 손님을 태우러 감
			taxi.cost -= to.cost;
		else // 손님을 목적지로 이동 시킨 경우
			taxi.cost += to.cost;
			
		return true;
	}
	return false;
}

int solve(tInfo taxi) {

	while (--M >= 0) {

		tInfo toPassenger = BFS(taxi.xy.x, taxi.xy.y, 1); //1번 손님의 위치 탐색
		if (!canGo(taxi, toPassenger, 1)) //2번 손님으로 이동 가능하다면 택시 정보 갱신
			return -1;

		tInfo toDestination = BFS(taxi.xy.x, taxi.xy.y, 2); //3번 목적지의 거리와 좌표 탐색
		if (!canGo(taxi, toDestination, 2))  // 목적지로 이동 가능하다면 택시 정보 갱신
			return -1;

		passengers[toPassenger.xy.x][toPassenger.xy.y] = { -1,-1 }; //하차 후 손님 좌표의 정보 삭제
	}

	return taxi.cost;
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int x, y, cost;
	
	tInfo taxi;
	
	cin >> N >> M >> cost;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) {
			cin >> tMap[i][j];
			passengers[i][j] = { -1,-1 }; //도착지의 정보가 0,0이 될 수 있기 때문에 -1로 초기화
		}
	
	cin >> x >> y;
	taxi = { {x - 1, y - 1}, cost };
	
	for (int i = 0; i < M; i++) {
		int x, y, next_x, next_y;
		cin >> x >> y >> next_x >> next_y;
		passengers[x - 1][y - 1] = { next_x - 1 , next_y - 1}; //출발지와 도착지 매핑
	}

	cout << solve(taxi);
}