[BOJ][삼성기출] 19238. 스타트 택시

gyeong·2021년 4월 24일
0

PS

목록 보기
45/46

문제

스타트 택시


첫인상

구현은 어렵지 않아 보이는데, 정답률이 19%라 예외케이스가 많을 것 같았고 실제로도 그랬다.

0. 최단경로를 찾는 문제이니 BFS로 풀면 되겠다.

1. 다음으로 태울 승객을 어떻게 고를 것인가?

현재 택시의 위치에서 최단거리가 가장 짧은 승객부터 고르도록 한다.

2. 손님과 택시가 처음에 같은 위치에 있을 수 있나?

처음에 입력으로 주어질 때는 같은 위치에 있을 수 없을 것 같다.
그리고 문제 조건 중 '모든 출발지는 서로 다르다' 라는 조건이 있기 때문에 출발지점이 같은 경우는 고려하지 않아도 된다.

3. 이동 성공과 실패

택시는 (1) 손님을 태우고 (2) 목적지로 향한다.
한 칸을 이동할 때마다 연료를 1씩 소비하며, 이동 도중 연료가 0보다 작아지면 이동 실패로 간주한다.
손님을 태우고 목적지로 향하는 것을 성공하면 (연료가 0 이상일 때 목적지에 도착하는 경우), 손님을 태우고 이동하며 소비한 연료의 두 배가 다시 충전된다.


문제 접근

문제 흐름

  1. 현재 위치에서 최단거리가 가장 짧은 손님을 선택한다.
  2. 손님을 태운다.
  3. 손님을 태우고 목적지로 향한다.

이 과정을 M명의 손님에 대해 성공하면 이동을 성공한 것이고, 한 명의 손님에 대해서라도 실패하면 이동을 실패한 것이므로 -1을 반환한다.

변수 설정

손님의 출발점, 도착점에 대한 정보를 저장하는 구조체(node)를 따로 만들었다.
그리고 그 구조체의 벡터(Nodes)를 만들어 손님 정보를 따로 관리하였다.
BFS 알고리즘을 사용할 때 손님의 위치 정보를 참조하기 위해 손님의 정보만 따로 저장하는 맵 (People)을 따로 만들었다.

관건 0. 손님 고르기

구현: next_target()
알고리즘: BFS

택시로부터 모든 손님과의 거리를 구해야 한다.
최단거리의 손님이 여려 명이라면 (1) 행 번호가 낮을 수록 (2) 열 번호가 낮을 수록 우선순위를 가진다.

단순히 BFS를 돌며 손님을 고르게 했더니 1% 에서 바로 틀렸다. 질문검색 게시판을 통해 알아낸 실패의 이유는 벽으로 인해 최단거리에 위치한 손님에게 도달할 수 없는 경우를 고려하지 못해서다.

문제 조건에 손님에게 항상 도달할 수 있다는 조건이 없으므로 이를 고려해야 한다.

BFS 를 돌며 len_info 배열에 거리 값을 업데이트 한다. (len_info 배열은 처음에 -1 로 초기화.)
그 후 택시의 위치부터 맵의 특정 위치까지의 최소 거리를 구한다.

위 과정이 끝나면 (1, 1) 부터 People 배열을 탐색하며 사람이 있고, 그 사람이 아직 택시를 기다리고 있는 경우에 한해 최소 거리에 위치하는 손님을 구한다.
((1, 1) 부터 탐색하기 때문에 같은 최소거리에 위치한 사람이 여려 명일 경우 위쪽, 왼쪽에 위치한 사람 순으로 우선순위를 가지는 조건을 충족한다.)
최소 거리에 위치한 사람의 좌표 정보를 획득한 후, 해당 좌표가 len_info 배열에서 -1의 값을 가지고 있는지 확인한다.
값이 -1일 경우, 해당 좌표까지 도달할 수 없음을 의미하기에 이 경우는 이동을 실패한 것이다.

관건 1. 손님 태우기

손님까지 도달할 수 있다면 (len_info 배열의 값이 -1이 아닌 경우)
현재 연료량으로 손님까지 갈 수 있는지 확인한다.
도달 가능한 경우 택시를 손님의 위치로 이동시키고, 연료를 업데이트 한다.

관건 2. 목적지로 이동

구현: go_destination()
알고리즘: BFS

목적지로 이동하는 것도 손님을 고르는 것과 마찬가지로 벽으로 인해 목적지로 이동할 수 없는 경우를 고려해야 한다. 로직은 손님 고르기와 동일하다.


풀이

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <limits.h>
using namespace std;

typedef struct node {
	int x;
	int y;
	int dx;
	int dy;
	int is_done;
} node;

vector<node> Nodes;
int N, M, Fuel, Rst, Tx, Ty, Len;
int Map[21][21]; // 벽 정보
int People[21][21]; // 손님 정보
int Dx[] = { -1, 0, 0, 1 };
int Dy[] = { 0, -1, 1, 0 };

void input() {
	cin >> N >> M >> Fuel;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> Map[i][j];
		}
	}
	cin >> Tx >> Ty;
	memset(People, -1, sizeof(People));
	for (int i = 1; i <= M; i++) {
		int x, y, dx, dy;
		cin >> x >> y >> dx >> dy;
		People[x][y] = Nodes.size();
		Nodes.push_back({ x, y, dx, dy, 0 });
	}
	Rst = 0;
}

int is_range(int x, int y) {
	if (x >= 1 && x <= N && y >= 1 && y <= N) return true;
	return false;
}

int next_target() {
	int is_visit[21][21];
	int len_info[21][21];
	memset(is_visit, 0, sizeof(is_visit));
	memset(len_info, -1, sizeof(len_info));
	queue < pair<pair<int, int>, int> > Q;
	is_visit[Tx][Ty] = 1;
	Q.push(make_pair(make_pair(Tx, Ty), 0));

	while (!Q.empty()) { // 택시로부터 모든 맵까지의 거리 세팅
		int x = Q.front().first.first;
		int y = Q.front().first.second;
		int len = Q.front().second; 
		Q.pop();
		len_info[x][y] = len;
		for (int dir = 0; dir < 4; dir++) {
			int nx = x + Dx[dir];
			int ny = y + Dy[dir];
			if (is_visit[nx][ny]) continue;
			if (!Map[nx][ny] && is_range(nx, ny)) { // 벽이 없고, 아직 방문하지 않았고, 범위 내일 경우
				is_visit[nx][ny] = 1;
				Q.push(make_pair(make_pair(nx, ny), len + 1));
			}
		}
	}

	int min_len = INT_MAX;
	int target;
	for (int x = 1; x <= N; x++) {
		for (int y = 1; y <= N; y++) {
			if (People[x][y] != -1 && !Nodes[People[x][y]].is_done) { // 사람이 있고, 그 사람이 아직 종료 전
				if (len_info[x][y] == -1) return -1; // 그 사람까지 갈 수 없는 경우
				if (min_len > len_info[x][y]) { // 최소 거리를 업데이트
					min_len = len_info[x][y];
					target = People[x][y]; // 타겟 업데이트
				}
			}
		}
	}

	if (min_len < Fuel) {// 각 손님의 출발지와 목적지는 다르기 때문에 연료 거리보다 더 커야 한다.
		Fuel -= min_len;
		Tx = Nodes[target].x; Ty = Nodes[target].y; // 택시를 손님의 위치로 이동
		Nodes[target].is_done = 1;
		return target; //그 사람의 번호를 리턴
	}
	return -1; // 손님까지 도달할 수 있는 연료가 없을 경우
	
}

int go_destination(int num) {
	int is_visit[21][21];
	int len_info[21][21];
	memset(is_visit, 0, sizeof(is_visit));
	memset(len_info, -1, sizeof(len_info));
	queue < pair<pair<int, int>, int> > Q;
	is_visit[Tx][Ty] = 1;
	Q.push(make_pair(make_pair(Tx, Ty), 0));

	int dx = Nodes[num].dx; // 목적지 정보
	int dy = Nodes[num].dy;

	while (!Q.empty()) {
		int x = Q.front().first.first;
		int y = Q.front().first.second;
		int len = Q.front().second;
		Q.pop();
		len_info[x][y] = len;
		for (int dir = 0; dir < 4; dir++) {
			int nx = x + Dx[dir];
			int ny = y + Dy[dir];
			if (Map[nx][ny] != 1 && !is_visit[nx][ny] && is_range(nx, ny)) { // 벽이 없고, 아직 방문하지 않았고, 범위 내일 경우
				is_visit[nx][ny] = 1;
				Q.push(make_pair(make_pair(nx, ny), len + 1));
			}
		}
	}

	if (len_info[dx][dy] == -1) return false; // 도착지점으로 가는 길이 없는 경우
	if (len_info[dx][dy] <= Fuel) {// 도착과 동시에 연료가 0 되어도 된다.
		Fuel -= len_info[dx][dy];
		Fuel += len_info[dx][dy] * 2; // 연료 세팅
		Tx = dx; Ty = dy; // 택시를 목적지로 이동
		return true;
	}
	return false; // 도착지점까지 가는 길은 있으나 연료가 없는 경우
}

void solve(){
	int cnt = 0;
	while (true) {
		if (cnt == M) break; // M명의 손님을 다 옮겼을 경우 종료
		
		int num = next_target(); // 다음 손님 찾기
		if (num == -1) { // 연료가 바닥났을 경우
			Rst = -1;
			break;
		}
		
		int ret = go_destination(num);
		if (!ret) {
			Rst = -1;
			break;
		}
		else {
			cnt++;
		}
	}
}

int main() {
	input();
	solve();
	if (Rst == -1) {
		cout << Rst << endl;
	}
	else {
		cout << Fuel << endl;
	}
}
profile
내가 보려고 만든 벨로그

0개의 댓글