[코드트리] 자율주행 전기차 (삼성 SW 역량테스트 2020 상반기 오후 2번)

 

SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기)

 

삼성 A형 전체 링크

 

https://www.codetree.ai/training-field/frequent-problems/problems/autonomous-electric-car

이후 설명 및 입/출력은 링크 참고

 

자율주행 전기차 문제 풀이는 BOJ 19238 : 스타트 택시와 같다.

#include <stdio.h>

#define MAX (20 + 5)

int T;
int N, M, F;
int MAP[MAX][MAX];

typedef struct st1
{
	int r;
	int c;
}RC;

RC car;
RC queue[MAX * MAX];
int rp, wp;

typedef struct st2
{
	int sr;
	int sc;
	int er;
	int ec;
	int check;
}PEOPLE;

PEOPLE people[MAX * MAX];

typedef struct st3
{
	int peopleNumber;
	int length;
}INFO;

void input()
{
	scanf("%d %d %d", &N, &M, &F);

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = -1;

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			scanf("%d", &MAP[r][c]);
			if (MAP[r][c] == 1) MAP[r][c] = -1;
		}
	}

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

	for (int i = 1; i <= M; i++)
	{
		int sr, sc, er, ec;

		scanf("%d %d %d %d", &sr, &sc, &er, &ec);

		people[i].sr = sr;
		people[i].sc = sc;
		people[i].er = er;
		people[i].ec = ec;
	}
}

void output(int map[MAX][MAX])
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
			printf("%d ", map[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

INFO findPeople()
{
	int tmpMAP[MAX][MAX] = { 0 };
	int visit[MAX][MAX] = { 0 };

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			tmpMAP[r][c] = MAP[r][c];

	for (int i = 1; i <= M; i++)
	{
		if (people[i].check) continue;

		tmpMAP[people[i].sr][people[i].sc] = i;

		/* 승객의 출발지는 모두 다르지만, A 승객의 도착지와 B 승객의 출발지가 같을 수 있다. */
		if (people[i].sr == car.r && people[i].sc == car.c) return { i, 0 };
	}

	rp = wp = 0;

	queue[wp].r = car.r;
	queue[wp++].c = car.c;

	visit[car.r][car.c] = 1;

	int min = 0x7fff0000;
	int peopleNumber = -1;
	int minR = 100;
	int minC = 100;
	while (wp > rp)
	{
		RC out = queue[rp++];

		for (int k = 0; k < 4; k++)
		{
			int nr, nc;

			nr = out.r + dr[k];
			nc = out.c + dc[k];

			if (tmpMAP[nr][nc] == -1 || visit[nr][nc]) continue; /* 벽이거나 방문한 경우 */

			queue[wp].r = nr;
			queue[wp++].c = nc;

			visit[nr][nc] = visit[out.r][out.c] + 1;

			if (tmpMAP[nr][nc] != 0) /* 사람이 있는 경우 */
			{
				if ((visit[nr][nc] < min)
					|| (visit[nr][nc] == min && nr < minR)
					|| (visit[nr][nc] == min && nr == minR && nc < minC))
				{
					peopleNumber = tmpMAP[nr][nc];
					min = visit[nr][nc];
					minR = nr;
					minC = nc;
				}
			}
		}
	}

	return { peopleNumber, min - 1 };
}

int goToDestination(int er, int ec)
{
	int tmpMAP[MAX][MAX] = { 0 };
	int visit[MAX][MAX] = { 0 };

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			tmpMAP[r][c] = MAP[r][c];

	rp = wp = 0;

	queue[wp].r = car.r;
	queue[wp++].c = car.c;

	visit[car.r][car.c] = 1;

	while (wp > rp)
	{
		RC out = queue[rp++];

		if (out.r == er && out.c == ec) return visit[out.r][out.c] - 1;

		for (int k = 0; k < 4; k++)
		{
			int nr, nc;

			nr = out.r + dr[k];
			nc = out.c + dc[k];

			if (tmpMAP[nr][nc] == -1 || visit[nr][nc]) continue; /* 벽이거나 방문한 경우 */

			queue[wp].r = nr;
			queue[wp++].c = nc;

			visit[nr][nc] = visit[out.r][out.c] + 1;
		}
	}

	return -1;
}

int simulate()
{
	for (int i = 0; i < M; i++)
	{
		/* 남은 승객 중 가장 가까운 승객을 찾는다. */
		INFO info = findPeople();

		if (F <= info.length) return -1;

		F -= info.length; /* 연료 처리 */

		int peopleNumber = info.peopleNumber;

		if (peopleNumber == -1) return -1;

		car.r = people[peopleNumber].sr; /* 택시 이동 */
		car.c = people[peopleNumber].sc;

		/* 승객의 목적지를 찾는다. */
		int fuel = goToDestination(people[peopleNumber].er, people[peopleNumber].ec);

		if (fuel == -1 || F < fuel) return -1;

		F += fuel; /* F = F - fuel + fuel * 2, 도착한 경우, 소모한 연료 2배 증가 */

		car.r = people[peopleNumber].er; /* 이동 */
		car.c = people[peopleNumber].ec;
		people[peopleNumber].check = 1; /* 승객 처리 표시 */
	}

	return F;
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		printf("%d\n", simulate());
	}

	return 0;
}