boj, 백준) 19238. 스타트택시 ( C / C++ )

1. 문제 링크

www.acmicpc.net/problem/19238

19238번: 스타트 택시

2. 문제 개요

N*N의 맵이 있다. M명의 손님이 있고 각 손님은 시작점과 가고 싶은 점(도착점)이 있다.

택시는 매번 손님을 택시로부터 가장 가까운 손님을 태운다.

그리고 그 손님의 목적지까지 데려다준다.

태우고 데려다줄때마다 연료를 소모하는데 연료가 바닥이 나면 -1을 출력.

맵에 있는 모든 손님을 다 태워주고 나면 남은 연료를 출력.

 

3. 문제 힌트

이 문제는 그냥 예외상황을 잘 처리해주고 BFS의 개념을 잘 이해하고.. 여튼 함정카드가 꽤 있기 때문에 꼭 연습장 같은 곳에 미리 써보고 하는 걸 추천합니다.

처음에 쉽네~하고 접근했다가 왜 안되지.. 하면서 시간 잡아먹는 류의 문제입니다. 시험장에서 이러면 멘탈 박살.. 처음부터 플로우를 만들 때, 고려해야 할 점은 없을까 한 번 더 확인하면서 다음 단계로 넘어가야 합니다. BFS의 특성을 잘 알고 계셨다면 벽에 막혀있는 경우와 같은 예외상황을 바로 캐치하셨을 거라 생각합니다.

 

(1) 택시가 손님을 찾을 때 →BFS

    -거리가 같다면 위 → 조건문

          -행이 같으면 왼쪽 → 조건문

 

(2) 후보자 선택 완료 

     - 후보자까지 가는데 연료 OK? → 모자라면 종료

     - 선택 못하면 → 종료 (벽으로 둘러싸여 있음)

 

(3) 택시가 손님의 목적지까지 데려다줄 때 →BFS

     - 도착 못하면 → 종료 (도착지가 벽으로 둘러싸여 있음)

 

(4) 목적지 도착 완료

     - 연료 OK? → 연료 사용량의 2배 더해주기

     - 연료 모자라면 → 종료

 

(5) 사람 1명 줄이고

      - 0명? → 끝,

      - 1명 이상? →(1)로

 

대략 이 정도 고려해주면 될 거 같다.

 

 

4. 문제 풀이

3번 힌트에서 문제의 핵심 내용을 다 언급하고 있기 때문에 저 내용을 코드로 잘~옮기기만 하면 된다.

코드로 옮길 때 주의할 점을 여기서 설명해보면,

 

구조체는 택시, 손님, 탐색을 위한 좌표. 이렇게 3개를 선언해주었다.

 

택시가 활동할 영역을 map[21][21]변수로 선언해 주었고, 벽은 1이라고 주어지지만 1 이상의 값은 사람의 번호로 쓸 것이기 때문에 벽을 입력과 동시에 -1로 변경해주었다. 그래서 map의 값은 -1 : 벽, 0 : 공간 1~M : 사람이다.

map값을 사람으로 해주어야 그 사람을 상수 시간에 접근할 수 있기 때문에..(물론 그 외 방법도 있겠지만,)

 

택시의 정보를 입력받고,,

손님의 정보도 입력받고 맵에 표시해줍니다.

 

그리고 바로 손님을 찾으러 이동.

 

최단거리에 있는 손님을 찾을 때 벽만 없다면 그냥 모든 사람들을 한번 슥~ 훑으면서 찾을 수 있겠으나, 벽이 있기 때문에 BFS로 탐색해야만 합니다.

 

여기서 고려할 점은 거리가 0인 (택시와 같은 좌표에 있는) 사람도 탐색해주어야 하는 것.

그리고 구현에 약하신 분은 '거리가 같다면 가장 위쪽(낮은 행), 행이 같다면 가장 왼쪽(낮은 열)'이 걸 찾는 걸 어려워하실 거 같은데, BFS 할 때 Queue에 데이터가 쌓이는 원리를 알고 계신다면 쉽게 구현할 수 있을 것입니다.

 

Queue에 하나의 좌표가 쌓일 때는 가장 앞에 거리가 0인 좌표에서, 4방향으로 탐색해서 거리가 1인 좌표가 4개 이렇게 쌓입니다. 즉, 거리순으로 점점 쌓이게 되는데, '거리가 같다면'이라는 조건이 있기 때문에, 지금 후보의 거리보다 Queue front에 있는 거리가 더 크다면 더 이상 BFS탐색을 진행할 필요가 없어집니다.(점점 거리가 멀어지는 순으로 탐색을 하기 때문)

그래서 같은 거리 값을 가진 사람(좌표)들 중에서 조건을 만족하는 사람을 찾아야 하는데, 하나의 후보 사람(좌표)을 두고 값을 계속 갱신하는 방향으로 최종 후보자(태울 손님)를 결정해 냅니다.

이 부분은 코드로 보시면 바로 이해가 될 것 같습니다.

 

BFS탐색을 하면서 거리 값은 갖고 있을 테니 연료에서 빼주고, 모자라다면 끝..

그리고 손님은 존재하지만 태울 손님을 못 찾은 경우는 손님이 벽으로 둘러싸여 있다는 걸 의미하기 때문에 까먹지 말고 예외처리해줍시다.

 

이제 손님을 찾았으니까

사람을 태웠다는 의미로 map에서 제거해줍니다.

그리고 택시도 이동시켜주고 연료도 제거해줍니다.

 

이제 Queue를 비우고 다시 BFS를 시작해야 합니다.

손님을 태운 위치에서부터 시작해서 기존에 입력받았던 목표 좌표가 나올 때까지 BFS탐색을 시작합니다.

이 때 역시 도달하지 못했다면 벽에 둘러싸여 있는 상태기 때문에 예외처리를 꼭 해주고

 

장소를 찾았다면 연료 계산, 택시 이동 등을 해주고

연료가 모자라다면 종료하는 방식으로 진행해줍시다.

 

이제 한 사람에 대한 작업을 마쳤으니

전체 사람 (변수 m)을 1줄이고 

m==0이라면 반복문을 종료하고 그렇지 않으면 사람이 남아있다는 의미이기 때문에 손님을 찾으러 다시 반복해야 합니다.

 

5. 코드

#include <cstdio>
#include <queue>
#include <string.h>
using namespace std;

const int dx[] = { 1,-1,0,0 };
const int dy[] = { 0,0,1,-1 };

struct CAR
{
	int y, x;
	int fuel;
}Taxi;

struct PERSON
{
	int y, x;
	int goal_y, goal_x;
}Person[401];	//1~400

struct COORD 
{
	COORD(){}
	COORD(int y_, int x_, int dist_ = 0) { y = y_; x = x_; dist = dist_; }
	int y, x;
	int dist;
};

int n, m;
int map[21][21];

int main()
{
	scanf("%d %d %d", &n, &m, &Taxi.fuel);

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= n; ++j) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 1)
				map[i][j] = -1;
		}

	scanf("%d %d", &Taxi.y, &Taxi.x);

	for (int i = 1; i <= m; ++i) {
		scanf("%d %d %d %d", &Person[i].y, &Person[i].x, &Person[i].goal_y, &Person[i].goal_x);
		map[Person[i].y][Person[i].x] = i;
	}
	

	while (1)
	{
		queue<COORD> q;
		bool visited[21][21];
		memset(visited, false, sizeof(visited));

		visited[Taxi.y][Taxi.x] = true;
		q.push(COORD(Taxi.y, Taxi.x));

		int candinum = -1;
		COORD candi;
		int usefuel = 0;

		while (!q.empty())
		{
			COORD cur = q.front(); q.pop();

			if (map[cur.y][cur.x] > 0)
			{
				if (candinum == -1)
				{
					candinum = map[cur.y][cur.x];
					candi = cur;
					usefuel = cur.dist;
				}
				else
				{
					if (candi.dist < cur.dist)
						break;

					if (candi.y > cur.y)
					{
						candinum = map[cur.y][cur.x];
						candi = cur;
						usefuel = cur.dist;
					}
					else if (candi.y == cur.y)
					{
						if (candi.x > cur.x)
						{
							candinum = map[cur.y][cur.x];
							candi = cur;
							usefuel = cur.dist;
						}
					}
				}
			}

			for (int dir = 0; dir < 4; ++dir)
			{
				COORD next;
				next.y = cur.y + dy[dir];
				next.x = cur.x + dx[dir];
				next.dist = cur.dist + 1;

				if (next.y < 1 || next.x < 1 || next.x > n || next.y > n || visited[next.y][next.x] || map[next.y][next.x] == -1)
					continue;

				visited[next.y][next.x] = true;
				q.push(next);
			}

		}

		if (candinum != -1) {
			map[Person[candinum].y][Person[candinum].x] = 0;
			Taxi.y = Person[candinum].y;
			Taxi.x = Person[candinum].x;
			Taxi.fuel -= usefuel;

			if (Taxi.fuel < 0)
			{
				printf("-1");
				break;
			}

		}
		else
		{
			printf("-1");
			break;
		}
		
		q = queue<COORD>();
		memset(visited, false, sizeof(visited));

		visited[Taxi.y][Taxi.x] = true;
		q.push(COORD(Taxi.y, Taxi.x));

		bool arrived = false;
		int usefuelarrived = 0;

		while (!q.empty())
		{
			COORD cur = q.front(); q.pop();

			if (cur.y == Person[candinum].goal_y && cur.x == Person[candinum].goal_x)
			{
				arrived = true;
				usefuelarrived = cur.dist;
				break;
			}

			for (int dir = 0; dir < 4; ++dir)
			{
				COORD next;
				next.y = cur.y + dy[dir];
				next.x = cur.x + dx[dir];
				next.dist = cur.dist + 1;

				if (next.y < 1 || next.x < 1 || next.x > n || next.y > n || visited[next.y][next.x] || map[next.y][next.x] == -1)
					continue;

				visited[next.y][next.x] = true;
				q.push(next);
			}
		}

		if (!arrived)
		{
			printf("-1");
			break;
		}

		Taxi.y = Person[candinum].goal_y;
		Taxi.x = Person[candinum].goal_x;
		Taxi.fuel -= usefuelarrived;

		if (Taxi.fuel < 0)
		{
			printf("-1");
			break;
		}


		Taxi.fuel += (usefuelarrived * 2);
		--m;

		if (m == 0)
		{
			printf("%d", Taxi.fuel);
			break;
		}
	}


	return 0;
}

 

 

6. 결과