[코드트리] 자율주행 전기차

문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/autonomous-electric-car/submissions?page=2&pageSize=20

💻 문제 풀이 : C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>

#define MAX_MAP_SIZE 25

using namespace std;

struct Passenger {
	int rs, cs,re, ce;
	int dist;
	int state;
};

struct Coord {
	int row, col;
};

int N, M, C;
int MAP[MAX_MAP_SIZE][MAX_MAP_SIZE];
int car_r, car_c;
vector<Passenger> passenger;

int dr[] = { 0, 0, -1, 1 };
int dc[] = { -1, 1, 0, 0 };

bool cmp(Passenger A, Passenger B)
{
	if (A.rs < B.rs) return true;
	if (A.rs > B.rs) return false;
	if (A.cs < B.cs) return true;
	if (A.cs > B.cs) return false;
	return false;
}

int inRange(Coord c)
{
	if (c.row <= 0 || c.col <= 0 || c.row > N || c.col > N)
		return 0;
	else
		return 1;
}

int getDist(int idx, int re, int ce)
{
	if (car_r == re && car_c == ce)
	{
		passenger[idx].dist = 0;
		return 0;
	}
	int visited[MAX_MAP_SIZE][MAX_MAP_SIZE] = { 0 };
	queue<Coord> nowQ;
	nowQ.push({ car_r,car_c });
	visited[car_r][car_c] = 1;
	while (!nowQ.empty())
	{
		Coord now = nowQ.front();
		nowQ.pop();
		for (int i = 0; i < 4; i++)
		{
			Coord next = { now.row + dr[i], now.col + dc[i] };
			if (!inRange(next)) continue;
			if (next.row == re && next.col == ce)
			{
				passenger[idx].dist = visited[now.row][now.col];
				return visited[now.row][now.col];
			}
			if (MAP[next.row][next.col] == 1) continue;
			if (visited[next.row][next.col] != 0) continue;
			visited[next.row][next.col] = visited[now.row][now.col] + 1;
			if (visited[next.row][next.col] > C) continue;
			nowQ.push(next);
		}
	}
	return 2134567890;
}

int isRideOkay()
{
	int minDist = 2134567890;
	int minIdx = -1;
	for (int i = 1; i < passenger.size(); i++)
	{
		// 승객이 이미 택시 이용한 경우
		if (passenger[i].state != 0) continue;
		int tmpDist = getDist(i, passenger[i].rs, passenger[i].cs);
		if (minDist > tmpDist)
		{
			minDist = tmpDist;
			minIdx = i;
		}
	}
	return minIdx;
}

void CLEAR()
{
	memset(MAP, 0, sizeof(MAP));
}

void INPUT()
{
	cin >> N >> M >> C;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			cin >> MAP[i][j];
		}
	}
	cin >> car_r >> car_c;
	// 승객 1번부터 시작
	passenger.push_back({ 0, 0, 0, 0, 0, 0 });
	for (int i = 0; i < M; i++)
	{
		int x_s, y_s, x_e, y_e;
		cin >> x_s >> y_s >> x_e >> y_e;
		passenger.push_back({ x_s, y_s, x_e, y_e, 0, 0 });
	}
	sort(passenger.begin(), passenger.end(), cmp);
}

void SOLVE()
{
	int dist = 0;
	int time = 0;
	while (time < 1000)
	{
		int target = isRideOkay();
		// 1. 승객과의 거리 판단
		if (target < 0)
		{
			break;
		}
		// 4. 출발지로 이동하고 배터리 소모
		car_r = passenger[target].rs;
		car_c = passenger[target].cs;
		C = C - passenger[target].dist;
		passenger[target].state = 1;
		// 5. 도착지로 이동
		dist = getDist(target, passenger[target].re, passenger[target].ce);
		// 운행 도중 배터리를 소모한 경우 즉시 종료
		if (dist > C)
		{
			C = 0;
			break;
		}
		else {
			C += dist;
			car_r = passenger[target].re;
			car_c = passenger[target].ce;
		}
		time++;
	}

	if (time == 0)
	{
		cout << -1 << endl;
		return;
	}

	cout << C << endl;
}

int main()
{
	CLEAR();
	INPUT();
	SOLVE();

	return 0;
}

📌 memo 😊