[백준] [19238번] 스타트 택시

www.acmicpc.net/problem/19238

19238번: 스타트 택시

문제

스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.

 

택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.

 

M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.

 

백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.

 

입력

첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.

다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.

다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.

그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

출력

모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.

 

 

풀이과정 (시뮬레이션 + bfs & c++)

1. 가장 가까운 고객을 찾는 BFS 함수인 findNearUser함수를 구현하였다.

2. 목적지까지 최단 경로로 진행하는 BFS 함수를 구현하였다.

* 둘다 BFS를 이용했지만, 목적이 달라 두 함수를 만듬.

 

예외 사항을 생각하지 못해 시간이 오래 걸린 문제였다.

1. 도착점에 새로운 고객이 있는 경우

 -> 도착점으로 이동 후 그 지점에 고객이 있는 경우 체크를 하지 못했었다. (상하좌우만을 체크하고 현 지점은 방문한 것으로 체크했기 때문이다..)

 

 

소스코드

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

struct user {
	int curX;
	int curY;
	int desX;
	int desY;
}typedef user;

pair<int, int> curPos;
vector<user> userList;
int map[20][20];

int N, M, L; // N*N, M명, 연료
int L1, L2;
int dx[4] = { 1,-1,0,0};
int dy[4] = { 0,0,1,-1};
int answer = 0;

int findNearUser() {
	queue<pair<int, int>> que;
	int visited[20][20] = { 0, };
	int dist = 0;
	int isFindUser = 0;
	pair<int, int> findUser;
	if (map[curPos.second][curPos.first] >= 2) {
		isFindUser = 1;
		findUser = make_pair(curPos.first, curPos.second);
	}
	else {
		que.push(make_pair(curPos.first, curPos.second));
		visited[curPos.second][curPos.first] = 1;
		while (!que.empty() && !isFindUser) {
			int queSize = que.size();
			for (int i = 0; i < queSize; i++) {
				pair<int, int> p = que.front(); que.pop();
				for (int j = 0; j < 4; j++) {
					int nx = p.first + dx[j];
					int ny = p.second + dy[j];
					if (nx < 0 || ny < 0 || nx >= N || ny >= N || map[ny][nx] == 1) continue;
					if (visited[ny][nx] == 1) continue;
					if (isFindUser && map[ny][nx] >= 2) {
						if (findUser.second > ny) {
							findUser = make_pair(nx, ny);
						}
						else if (findUser.second == ny && findUser.first > nx) {
							findUser = make_pair(nx, ny);
						}
					}
					else if (map[ny][nx] >= 2) {
						findUser = make_pair(nx, ny);
						isFindUser = 1;
					}
					pair<int, int> np = make_pair(nx, ny);
					que.push(np);
					visited[ny][nx] = 1;
				}
			}
			dist++;
			L--;
			if (L <= 0) {
				return 0;
			}
		}
	}
	if (isFindUser) {
		curPos.first = findUser.first;
		curPos.second = findUser.second;
		L1 = dist;
		return 1;
	}
	return 0;
}
int goToDestination(int desX, int desY) {
	if (curPos.first == desX && curPos.second == desY) {
		return 1;
	}
	queue<pair<int, int>> que;
	int visited[20][20] = { 0, };
	int dist = 0;

	que.push(make_pair(curPos.first, curPos.second));
	visited[curPos.second][curPos.first] = 1;

	while (!que.empty()) {
		int queSize = que.size();
		
		for (int i = 0; i < queSize; i++) {
			pair<int, int> p = que.front(); que.pop();
			for (int j = 0; j < 4; j++) {
				int nx = p.first + dx[j];
				int ny = p.second + dy[j];
				if (nx < 0 || ny < 0 || nx >= N || ny >= N || map[ny][nx] == 1) continue;
				if (visited[ny][nx] == 1) continue;
				pair<int, int> np = make_pair(nx, ny);
				que.push(np);
				visited[ny][nx] = 1;
				if (nx == desX && ny == desY) {
					curPos.first = desX;
					curPos.second = desY;
					L2 = dist+1;
					L--;
					if (L < 0) {
						return 0;
					}
					return 1;
				}
			}
		}
		dist++;
		L--;
		if (L <= 0) { return 0; }
	}
	return 0;
}

int solution() {
		int userCount = 0;
	while (userCount < userList.size()) {
		L1 = 0; //for debug
		L2 = 0;
		//가장 가까운 고객을 찾음
		if (findNearUser()) {
			int nx, ny;
			for (int i = 0; i < M; i++) {
				//고객의 목적지를 찾는 코드.
				if (userList[i].curX == curPos.first &&
					userList[i].curY == curPos.second) {
					map[curPos.second][curPos.first] -= (i + 2);
					nx = userList[i].desX;
					ny = userList[i].desY;
					break;
				}
			}
			//고객을 목적지까지 데려다 줌
			if (goToDestination(nx, ny)) {
				L += (L2 + L2);
				userCount++;
			}
			else {
				//불가할 경우 종료
				return -1;
			}

		}
		else {
			//고객을 못찾는 경우
			return -1;
		}
	}
	return L;
}
int main()
{
	scanf("%d %d %d", &N, &M, &L);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	int x, y;
	scanf("%d %d", &y, &x);
	curPos = make_pair(x - 1, y - 1);
	for (int i = 0; i < M; i++) {
		int x1, y1, x2, y2;
		scanf("%d %d %d %d", &y1, &x1, &y2, &x2);
		map[y1 -1][x1 -1] = i + 2;
		user _user = { x1 -1, y1 -1, x2-1, y2 -1};
		userList.push_back(_user);
	}

	answer = solution();
	printf("%d\n", answer != -1 ? L : -1);
}

 

결과