(c++)백준 19238번: 스타트 택시

www.acmicpc.net/problem/19238

19238번: 스타트 택시

 

[풀이]

2020상반기 인턴 sw역량테스트에 나왔던 문제다. 1번 문제 푸느라 제대로 풀지 못했다..

다음과 같은 순서로 구현하였다.

1. 가까운 승객 찾기

2. 승객에게 이동: oil-출발지까지 이동거리, 택시 위치 승객 출발지로

3. 목적지로 이동: oil-목적지까지 이동거리

4. 남은 오일이 0보다 작으면 -1출력 후 끝, 0 이상이면 oil+목적지까지 이동거리*2

※getDist함수에서 승객의 출발지나 목적지에 도달하지 못하는 경우도 반환해줘야 한다!

 

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

struct Passenger {
	int startx, starty;
	int destx, desty;
	bool arrive;//도착정보
};

struct Pos {
	int x, y;
	int d;
};

int N, M, oil;
int Map[21][21];
Passenger pass[401];//인덱스 1~M
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };
bool visited[21][21];//최단 거리 찾기에 사용
int taxiX, taxiY;//택시 출발점
int Pnum;//태울 승객
int MinDist;

int getDist(int destx, int desty) {
	memset(visited, false, sizeof(visited));
	queue<Pos>q;
	q.push({ taxiX,taxiY,0 });
	visited[taxiX][taxiY] = true;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int d = q.front().d;
		q.pop();
		if (x == destx && y == desty)
			return d;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx <= 0 || nx > N || ny <= 0 || ny > N)
				continue;
			if (Map[nx][ny] != 1 && visited[nx][ny] == false) {
				visited[nx][ny] = true;
				q.push({ nx,ny,d + 1 });
			}
		}
	}
	return -1;
}

bool todest(int pn) {
	int d = getDist(pass[pn].destx, pass[pn].desty);
	if (d == -1)
		return false;
	//가는 도중 연료 다 떨어지면
	oil -= d;
	if (oil < 0)
		return false;
	//갈 수 있으면 승객 도착 표시, 소모된 연료*2 더하기
	pass[pn].arrive = true;
	oil += 2 * d;
	return true;
}

void findP() {
	//가까운 승객 찾기
	MinDist = 987654321;
	for (int p = 1; p <= M; p++) {
		//이미 태웠던 승객이면
		if (pass[p].arrive == true)
			continue;
		int px = pass[p].startx;
		int py = pass[p].starty;
		//승객과 거리 구하기
		int d = getDist(px, py); 
		if (d == -1)
			continue;
		if (MinDist > d) {
			Pnum = p;
			MinDist = d;
		}
		else if (MinDist == d) {
			//행이 같으면
			if (pass[p].startx == pass[Pnum].startx) {
				//열이 작은걸로
				if (pass[p].starty < pass[Pnum].starty)
					Pnum = p;
			}
			else if (pass[p].startx < pass[Pnum].startx)
				Pnum = p;
		}
	}
	//승객 데리러가기!
}

bool End() {
	for (int i = 1; i <= M; i++) {
		if (pass[i].arrive == false)
			return false;
	}
	return true;
}

void solution() {
	cin >> N >> M >> oil;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> Map[i][j];
		}
	}
	cin >> taxiX >> taxiY;
	for (int i = 1; i <= M; i++) {
		cin >> pass[i].startx >> pass[i].starty >> pass[i].destx >> pass[i].desty;
		pass[i].arrive = false;
	}
	while (!End()) {
		findP();
		//승객까지 가는데 쓰이는 연료
		oil -= MinDist;
		//택시 승객 출발지점으로
		taxiX = pass[Pnum].startx;
		taxiY = pass[Pnum].starty;
		//연료 안 떨어지고 갈 수 있는지
		if (!todest(Pnum)) {
			oil = -1;
			break;
		}
		taxiX = pass[Pnum].destx;
		taxiY = pass[Pnum].desty;
	}
	cout << oil << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solution();
	return 0;
}