백준 19238 - 스타트 택시

문제 링크입니다 https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

 

삼성 SW 역량 테스트 문제입니다. BFS를 이용하여 풀었습니다.

 

 

1. 현재 택시의 좌표에서 가장 가까운 손님에게 찾아간 뒤, 목적지까지 간다.

2. 목적지에서 가장 가까운 손님을 찾아간 뒤, 손님의 목적지까지 간다.

   2 - 1. 가장 가까운 손님이 많을 경우, 행이 작은순으로

          행이 같은 손님이 있을 경우 열이 작은 순으로 정렬한다.

3. 1번과 2번을 반복한다.

    3 - 1. 반복하는 도중, 연료가 부족할 경우 -1 출력

    3 - 2. 손님을 모두 태웠을 경우, 남은 연료 출력

 

 

접근 방법

 

1.  손님을 저장하는 구조체, 택시의 정보를 저장하는 구조체를 만든후, 구조체 백터를 사용해 손님을 저장한다.

2. 손님의 위치부터 목적지까지의 거리를 먼저 확인한다.

3. 택시부터 손님까지의 거리를 확인한다. 벽 때문에 못가는 경우도 있으니 bool 변수를 하나 만들어 도착했을 경우에만 true로 바꿔준다.

4. 조건에 따라 정렬한다.

5. 도달할 수 있는 경우라면 맨 앞의 백터값을 이용해 택시의 정보를 수정한다.

6. 모든 손님을 태우지 못했거나, 연료가 떨어졌을 경우에는 -1를 출력한다.

7. 3번부터 6번까지 반복한다.

  

 

정렬 코드에 대해서 설명하겠습니다. 

bool cmp(customer a, customer b) {
	if (a.dis_taxi < b.dis_taxi) return true;
	else if (a.dis_taxi == b.dis_taxi) {
		if (a.x < b.x) {
			return true;
		}
		else if (a.x == b.x) {
			if (a.y < b.y) return true;
			return false;
		}
		return false;
	}
	return false;
}

첫번째로 거리를 비교합니다. 거리가 다를 경우, A < B라면 정렬을 해줄 필요가 없으므로 참, A > B라면 정렬이 필요함으로 거짓을 return합니다.

거리가 같은 경우에는 두번째로 행을 비교해줍니다. 행이 작은 순서라는 것은 X값이 작다는 의미입니다. 거리와 같은 원리로 정렬합니다.

X값까지 같은 경우에는 세번째로 열을 비교합니다. 열이 적은 순서라는 것은 Y값이 작다는 의미입니다. 거리와 같은 원리로 정렬합니다.

 

 

두개의 BFS에 대해서 설명하겠습니다.

 

dis_want() 와 distance_customer()는 같은 방식으로 코드가 짜여져 있습니다.

1. 손님의 정보가 저장되어있는 만큼 for문 돌리기(memset으로 check배열 초기화 하는것 잊지마세요)

2. queue에 시작점과 거리(0) 저장하기

3. queue가 빌때까지 4방향 탐색 실행

4. 조건에 맞을 경우 queue에 저장(거리 1씩 증가하는 것 잊지마세요)

5. 탈출 조건에 맞을 경우 탈출한다

 

 

자세한 것은 코드를 참고해주세요!

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>
using namespace std;

int miro[21][21];
int check[21][21];
int arr[4] = { 0,1,0,-1 };
int arr2[4] = { 1,0,-1,0 };
int N, M, K;
typedef struct customer {
	int x;
	int y;
	int want_x;
	int want_y;
	int dis_taxi;
	int dis_goal;
	bool can = false;
}customer;
vector<customer> C;
vector<customer> S;
typedef struct taxi {
	int x;
	int y;
	int fuel;
	int num;
}taxi;
taxi T;

void distance_customer() {
	for (int k = 0; k < C.size(); k++) {
		memset(check, 0, sizeof(check));
		queue<pair<pair<int,int>, int>> q;
		check[C[k].x][C[k].y] = 1;
		C[k].can = false;
		q.push(make_pair(make_pair(C[k].x, C[k].y),0));
		while (!q.empty()) {
			int x1 = q.front().first.first;
			int y1 = q.front().first.second;
			int dis = q.front().second;
			if (x1 ==  T.x && y1 == T.y) {
				C[k].dis_taxi = dis;
				C[k].can = true;
				break;
			}
			q.pop();
			for (int i = 0; i < 4; i++) {
				int xx = x1 + arr[i];
				int yy = y1 + arr2[i];
				if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) {
					if (check[xx][yy] == 0 && miro[xx][yy] == 0) {
						check[xx][yy] = 1;
						q.push(make_pair(make_pair(xx,yy),dis + 1));
					}
				}
			}
		}
	}
}
void dis_want() {
	for (int k = 0; k < C.size(); k++) {
		memset(check, 0, sizeof(check));
		queue<pair<pair<int, int>, int>> q;
		check[C[k].x][C[k].y] = 1;
		q.push(make_pair(make_pair(C[k].x, C[k].y), 0));
		while (!q.empty()) {
			int x1 = q.front().first.first;
			int y1 = q.front().first.second;
			int dis = q.front().second;
			if (x1 == C[k].want_x && y1 == C[k].want_y) {
				C[k].dis_goal = dis;
				break;
			}
			q.pop();
			for (int i = 0; i < 4; i++) {
				int xx = x1 + arr[i];
				int yy = y1 + arr2[i];
				if (xx >= 1 && xx <= N && yy >= 1 && yy <= N) {
					if (check[xx][yy] == 0 && miro[xx][yy] == 0) {
						check[xx][yy] = 1;
						q.push(make_pair(make_pair(xx, yy), dis + 1));
					}
				}
			}
		}
	}
}
bool cmp(customer a, customer b) {
	if (a.dis_taxi < b.dis_taxi) return true;
	else if (a.dis_taxi == b.dis_taxi) {
		if (a.x < b.x) {
			return true;
		}
		else if (a.x == b.x) {
			if (a.y < b.y) return true;
			return false;
		}
		return false;
	}
	return false;
}

void solve() {
	dis_want();
	while (1) {
		distance_customer();
		sort(C.begin(), C.end(), cmp);
		/*for (int i = 0; i < C.size(); i++) {
			cout << C[i].dis_taxi << "\n";
		}*/

		if (T.fuel >= C[0].dis_goal + C[0].dis_taxi && C[0].can) {
			T.fuel = T.fuel - C[0].dis_taxi + C[0].dis_goal;
			T.x = C[0].want_x;
			T.y = C[0].want_y;
			T.num++;
		}

		else {
			if (T.num < M) {
				cout << "-1";
				break;
			}
		}

		if (T.num == M) {
			cout << T.fuel;
			break;
		}

		for (int i = 0; i < C.size() -1; i++) {
			S.push_back(C[i + 1]);
		}
		C.clear();
		for (int i = 0; i < S.size(); i++) {
			C.push_back(S[i]);
		}
		S.clear();
	}
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> miro[i][j];
		}
	}
	cin >> T.x >> T.y;
	T.fuel = K;
	T.num = 0;
	for (int i = 1; i <= M; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		C.push_back({ a,b,c,d,0,0});
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!