[삼성역량테스트] 19238 스타트택시

 

풀이일시 : 2021-01-24

 

 

문제 : 

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

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

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

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

<그림 1>

<그림 1>은 택시가 활동할 영역의 지도를 나타내며, 택시와 세 명의 승객의 출발지와 목적지가 표시되어 있다. 택시의 현재 연료 양은 15이다. 현재 택시에서 각 손님까지의 최단거리는 각각 9, 6, 7이므로, 택시는 2번 승객의 출발지로 이동한다.

<그림 2>

<그림 3>

<그림 2>는 택시가 2번 승객의 출발지로 가는 경로를, <그림 3>은 2번 승객의 출발지에서 목적지로 가는 경로를 나타낸다. 목적지로 이동할 때까지 소비한 연료는 6이고, 이동하고 나서 12가 충전되므로 남은 연료의 양은 15이다. 이제 택시에서 각 손님까지의 최단거리는 둘 다 7이므로, 택시는 둘 중 행 번호가 더 작은 1번 승객의 출발지로 이동한다.

<그림 4>

<그림 5>

<그림 4>와 <그림 5>는 택시가 1번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 남은 연료의 양은 15 - 7 - 7 + 7×2 = 15이다.

<그림 6>

<그림 7>

<그림 6>과 <그림 7>은 택시가 3번 승객을 태워 목적지로 이동시키는 경로를 나타낸다. 최종적으로 남은 연료의 양은 15 - 5 - 4 + 4×2 = 14이다.

모든 승객을 성공적으로 데려다줄 수 있는지 알아내고, 데려다줄 수 있을 경우 최종적으로 남는 연료의 양을 출력하는 프로그램을 작성하시오.

 

 

입력 : 

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

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

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

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

ex)

6 3 15

0 0 1 0 0 0

0 0 1 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 1 0

0 0 0 1 0 0

6 5

2 2 5 6

5 4 1 6

4 2 3 5

 

 

출력 : 

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

ex)

14

 

 

풀이 : 

 

은근 세부조건이 많았고 풀이시간 또한 지금껏 가장 길었다.. (드러난 나의 레벨ㅋㅋ)

정답 비율또한 18%로 매우 낮다.

 

기본적으로 문제는 최단거리를 계속 찾아야 하기 때문에 BFS를 사용한다.

 

또한 최단거리를 찾는 부분은 두가지로 나눌 수 있다.

1. 빈 택시가 손님에게로 가는 과정에서의 최단거리

2. 손님을 태우고 목표 지점으로 가는 과정에서의 최단거리

 

주의사항 1 - 동일한 거리의 사람을 포착했을 경우에는 행, 열 로 우선순위를 결정한다.

주의사항 2 - 출발지와 도착지가 동일할 수 있다.

ex) MAP에 A사람의 도착지를 3 으로 표시하고 B사람의 출발지를 2로 표시했다면 먼저 수행한 A사람의 도착지정보 3은 사라질 것이다. 그래서 vector를 이용했고 도착지정보는 따로 표시하지 않았다.

주의사항 3 - 벽만 아니라면 택시는 지나갈 수 있다. (사람이 서있어도 지나갈수있다.)

 

나머지는 코드의 주석으로 설명 (코드가 길다.)

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

using namespace std;

int dx[] = { -1,0,1,0 }; //row
int dy[] = { 0,1,0,-1 }; //col

struct group {
	int r;
	int c;
};

struct one {
	int X_;
	int Y_;
	int C_;
};

group man[MAX][MAX];
int N, M, f;
int map[MAX][MAX];
int r, c;
int rX, rY;
int visit[MAX][MAX] = { 0, };
int X1 = 0, Y1 = 0, C1 = 0;
int X2 = 0, Y2 = 0, C2 = 0;
int chk;

one bfs(int x, int y,int cnt, int func) {
	chk = 0; //chk가 0인 상태로 나간다면 아무것도 찾지 못했다는 것
	one re = { 0, };
	if (func == 1) { //func 1이라는건 사람을 찾는 bfs
		if (map[x][y] == 2) { //자기자신이 목표 좌표일경우
			re.X_ = x;
			re.Y_ = y;
			re.C_ = 0;
			chk = 1;
			return re; //기름한방울 안쓰고 그대로 return
		}
	}
	else if (func == 2) { //func 2라는건 목표점을 찾는 bfs
		if ((x==rX)&&(y==rY)) { //자기자신이 목표 좌표일경우
			re.X_ = x;
			re.Y_ = y;
			re.C_ = 0;
			chk = 1;
			return re; //기름한방울 안쓰고 그대로 return
		}
	}
	queue<pair<pair<int, int>, int>>q; //좌표,좌표,거리 가 큐에 담길것
	q.push({ { x,y },cnt }); //일반적인 bfs를 돌려준다.
	visit[x][y] = 1;
	int X = MAX; //x와 y, c는 최대값에서부터 최소값이 나올때마다 갱신된다.
	int Y = MAX;
	int C=987654321; //이부분을 실수했었다. C는 21 이상일 수 있는데 21로 잡아놨었다.
	while (!q.empty()) {
		int nx = q.front().first.first;
		int ny = q.front().first.second;
		int c = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nnx = nx + dx[i];
			int nny = ny + dy[i];
			int nc = c + 1;
			if (nnx > 0 && nnx <= N && nny > 0 && nny <= N && visit[nnx][nny]==0) {
				if (func == 1) { //func 1이라는건 사람을 찾는 bfs
					if (map[nnx][nny] == 2) { //map에 사람이 있는상황
						chk = 1; //찾았으니 체크
						if (nc <= C) { //nc가 C보다 작은상황에만 수행하자 크면 의미없잖아
							if (X > nnx) { //행이 작은상황이라면
								X = nnx,Y= nny,C = nc;
								re.X_ = X,re.Y_ = Y,re.C_ = C;
							}
							else if (X == nnx) { //행이 동일하다면
								if (Y >= nny) { //열을 비교해주고 넣어준다.
									X = nnx,Y = nny,C = nc;
									re.X_ = X,re.Y_ = Y,re.C_ = C;
								}
							}
						}		
						q.push({ { nnx,nny },nc }); //갱신이 되던말던 지나칠수는 있으니 q에 push
						visit[nnx][nny] = 1; //visit도 했다
					}
					else if (map[nnx][nny] != 1) { //벽이 아니기만 한다면
						q.push({ { nnx,nny },nc }); //q에 push
						visit[nnx][nny] = 1;//visit
					}
				}
				else if (func == 2) { //func 2라는건 목표점을 찾는 bfs
					if ((nnx==rX)&&(nny==rY)) { //찾은거다. 끝내버리자
						chk = 1;
						re.X_ = nnx;
						re.Y_ = nny;
						re.C_ = nc;
						return re;
					}
					else if (map[nnx][nny] != 1&&visit[nnx][nny]==0) { //벽이 아니고 방문X
						q.push({ { nnx,nny },nc });
						visit[nnx][nny] = 1;
					}
				}
			}
		}
	}
	return re;
}

int solution(int x,int y,int f) {
	one re2;
	one re3;
	for (int i = 0; i < M; i++) {

		re2 = bfs(x, y, 0, 1); //다음에 돌아올때는 x와 y를 다시 정의해줘야될것
		map[re2.X_][re2.Y_] = 4; //사람이 있는 지점. map에 4로 지정해준다. 다음엔 사람찾을때 얘 안찾게끔
		group go = man[re2.X_][re2.Y_]; //go는 목표지점을 가리킨다.
		rX = go.r;
		rY = go.c; //목표위치를 찾았다.
		int fuel = f - re2.C_; //기름 쓴 양을 빼준다.
		if ((fuel < 0)||(chk==0)) //기름이 음수거나 아무것도 찾지못했다면 
			return 0;	
		memset(visit, 0, sizeof(visit)); //visit 배열 초기화

		//여기서 다시 bfs돌리면 될것이다. 목표는 사람이 아닌 자신의 깃발
		re3 = bfs(re2.X_, re2.Y_, 0, 2);
		int fuel2 = fuel - re3.C_;
		if ((fuel2 < 0)||(chk==0))
			return 0;
		fuel2 =  fuel2+(2 * re3.C_); //여기선 기름 양을 채워준다.
		f = fuel2;
		x = re3.X_;
		y = re3.Y_;
		memset(visit, 0, sizeof(visit));
	}
	return f;
}

int main() {
	cin >> N >> M >> f;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
		}
	}
	cin >> r >> c;
	for (int i = 0; i < M; i++) {
		int hr, hc, mr, mc;
		cin >> hr >> hc >> mr >> mc;
		man[hr][hc] = { mr,mc }; //각각의 목표를 담아준다. 
		map[hr][hc] = 2; //2는 사람이 있는 출발위치
	}

	int result = solution(r,c,f);
	if (result == 0)
		printf("-1");
	else
		cout << result << endl;
	return 0;
}

 

참고자료 : BFS

dbstndi6316.tistory.com/63

[기본문제풀이] BFS 너비우선탐색

참고자료 : memset

dbstndi6316.tistory.com/28

[개념정리] memset함수