[BOJ] 19238 스타트 택시 / C++

https://www.acmicpc.net/problem/19238

19238번: 스타트 택시

 

 

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>

#define MAX_N 21
#define MAX_M 401

using namespace std;

int N, M, fuel;
int MAP[MAX_N][MAX_N]; // -2: EMPTY, -1: 
int dist[MAX_N][MAX_N];

struct DRIVER {
	int r, c, t;
};

DRIVER driver;

struct INFO {
	int sr, sc, er, ec;
};

INFO info[MAX_M];

struct PASSENGER {
	int r, c;
};

PASSENGER passenger[MAX_M];

vector <DRIVER> passengerList;

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

bool flag = true; // 모든 승객이 목적지까지 도달할 수 있음

void input()
{
	scanf("%d %d %d", &N, &M, &fuel);
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			scanf("%d", &MAP[i][j]);
			MAP[i][j] -= 2;
		}
	}

	scanf("%d %d", &driver.r, &driver.c);

	for (int i = 1; i <= M; i++)
	{
		int sr, sc, er, ec;
		scanf("%d %d %d %d", &sr, &sc, &er, &ec);

		info[i] = { sr,sc,er,ec};
		passenger[i] = { sr,sc};
		MAP[sr][sc] = i; // MAP에 승객의 번호를 저장
	}
}

void initialize_dist()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			dist[i][j] = -1;
		}
	}
}


void print_dist()
{
	printf("\n>> print_dist()\n");
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			printf("%2d ", dist[i][j]);
		}
		printf("\n");
	}
}

void print_passengerList()
{
	printf("\n>> print_passengerList()\n");
	for (int i = 0; i < passengerList.size(); i++)
	{
		printf("[%d] r = %d, c = %d, t = %d\n", i, passengerList[i].r, passengerList[i].c, passengerList[i].t);
	}
}

bool cmp(const DRIVER &p1, const DRIVER &p2)
{
	if (p1.t < p2.t) return true;
	else if (p1.t == p2.t)
	{
		if (p1.r < p2.r) return true;
		else if (p1.r == p2.r)
		{
			return p1.c < p2.c;
		}
	}
	return false;
}

void getShortestDist()
{
	initialize_dist(); // dist 배열을 -1로 초기화
	passengerList.clear(); // 승객 리스트 초기화

	queue <DRIVER> q;
	driver.t = 0; // 택시기사의 거리 초기화
	dist[driver.r][driver.c] = 0;
	q.push(driver);

	while (!q.empty())
	{
		int cur_r = q.front().r;
		int cur_c = q.front().c;
		int cur_t = q.front().t;

		q.pop();

		for (int k = 0; k < 4; k++)
		{
			int nr = cur_r + dr[k];
			int nc = cur_c + dc[k];

			if (nr <= 0 || nr > N || nc <= 0 || nc > N || MAP[nr][nc] == -1 || dist[nr][nc] != -1) continue;
			q.push({ nr,nc,cur_t + 1 });
			dist[nr][nc] = cur_t + 1;
		}
	}
	//print_dist();

	for (int i = 1; i <= M; i++)
	{
		int r = passenger[i].r;
		int c = passenger[i].c;

		if (MAP[r][c] > 0)
		{
			if (dist[r][c] == -1) // 벽에 둘러싸인 승객이 존재
			{
				flag = false;
				return;
			}
			else if (fuel > dist[r][c]) // 승객을 데려다줄 수 있으면
			{
				passengerList.push_back({ r,c,dist[r][c] });
			}
		}
	}

	if (passengerList.size() > 0)
	{
		sort(passengerList.begin(), passengerList.end(), cmp);
	}
	else
	{
		flag = false;
		return;
	}

	//print_passengerList();
}

int choose_passenger()
{
	// passengerList가 존재함
	int r = passengerList[0].r;
	int c = passengerList[0].c;

	int passengerNum = MAP[r][c]; // 승객 번호
	return passengerNum;
}

int drive(int passengerNum)
{
	// 승객을 태우러 감
	int pr = passenger[passengerNum].r;
	int pc = passenger[passengerNum].c;

	//printf("승객 태우기 전... fuel = %d\n", fuel);
	fuel -= dist[pr][pc];
	//printf("승객 태우러 왔음... fuel = %d\n", fuel);
	if (fuel < 0)
	{
		return -1;
	}
	else
	{
		int er = info[passengerNum].er;
		int ec = info[passengerNum].ec;

		queue <DRIVER> q;
		driver.r = pr;
		driver.c = pc;
		driver.t = 0;

		initialize_dist();
		dist[driver.r][driver.c] = 0;
		q.push(driver);

		while (!q.empty())
		{
			int cur_r = q.front().r;
			int cur_c = q.front().c;
			int cur_t = q.front().t;

			q.pop();

			if (cur_r == er && cur_c == ec)
			{
				//printf("승객 데려다줌~~!\n");
				MAP[pr][pc] = -2; // 승객을 벽으로 바꿔줌
				driver.r = er;
				driver.c = ec; // 택시 기사 위치 업데이트
				fuel -= cur_t;

				//printf("fuel = %d\n", fuel);
				if (fuel < 0) return -1;
				else
				{
					fuel += (2 * cur_t);
					return fuel;
				}
			}

			for (int k = 0; k < 4; k++)
			{
				int nr = cur_r + dr[k];
				int nc = cur_c + dc[k];

				if (nr <= 0 || nr > N || nc <= 0 || nc > N || MAP[nr][nc] == -1 || dist[nr][nc] != -1) continue;
				q.push({ nr,nc,cur_t + 1 });
				dist[nr][nc] = cur_t + 1;
			}
		}
	}
	return -1;
}

int solve()
{
	int ret = -1;
	for (int i = 1; i <= M; i++)
	{
		flag = true;
		// 1. 현재 택시기사의 위치에서 승객간의 최단거리를 구한다
		getShortestDist();
		if (flag == false) return -1; // 벽에 둘러싸인 승객이 있을때 -> 실패

		// 2. 태우러 갈 승객의 번호를 정한다
		int passengerNum = choose_passenger();

		// 3. 승객을 목적지까지 데려다준다.
		ret = drive(passengerNum);
		if (ret == -1) return -1;
	}

	return ret;
}

int main(void)
{
	input();
	int answer = solve();
	printf("%d\n", answer);
	return 0;
}

 

이 문제도 주어진 테스트 케이스는 다 통과하는데 계속 틀렸습니다를 받았던 문제다.

알고보니 INFO info[MAX_M]으로 선언해야하는데 INFO info[MAX_N]으로 선언해서 버퍼 크기가 터져버렸던것..ㅎㅎ

제발 다시는 이런 실수 하지말자