BOJ 19238 : 스타트 택시 (삼성 SW TEST A형)

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

삼성 A형 전체 링크

www.acmicpc.net/workbook/view/1152 (A형 문제집)

www.acmicpc.net/problem/19238

문제를 자세히 읽어서 아래의 조건을 파악하는 것이 핵심이다.

1) 승객의 출발지는 모두 다르지만, A 승객의 도착지와 B 승객의 출발지가 같을 수 있다.

2) 승객의 출발지나 도착지가 벽으로 막혀서 찾을 수 없는 경우를 고려해야 한다.

먼저 구조체 3개가 필요하다.

RC : 좌표 저장 구조체

PEOPLE : 1 ~ M번 승객의 출발지와 도착지, 그리고 check를 이용하여 탑승 여부를 확인하는 구조체

INFO : 택시가 가장 가까운 승객을 찾을 때, 승객의 번호와 거리를 저장할 구조체

#define MAX (20 + 5)

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

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

RC taxi;
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;

MAP에는 승객의 번호를 마킹할 수 있으므로, 벽 1 → -1로 바꾼다.

그리고 주변을 -1로 만들어서 택시의 경계조건 처리를 쉽게 바꾼다.

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", &taxi.r, &taxi.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;
	}
}

simulate 함수는 아래와 같이 만든다.

1) 남은 승객 중 가장 가까운 승객을 찾는다(findPeople).

그 승객까지 걸리는 연료를 계산하고, 움직일 수 있다면 그 승객으로 taxi를 이동한다.

그렇지 않다면, 즉, 연료가 부족하거나, 가능한 승객이 없다면 -1을 return 한다.

2) 승객의 목적지까지 걸리는 연료를 계산한다(goToDestination).

해당 연료로 목적지까지 움직일 수 있다면 움직이고 해당 승객은 탑승 처리로 표시한다.

그렇지 않다면, 즉, 연료가 부족한 경우 -1을 return 한다.

3) 이 과정을 M번 성공하면 남아있는 연료 F를 return 한다.

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;

		taxi.r = people[peopleNumber].sr; /* 택시 이동 */
		taxi.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배 증가 */

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

	return F;
}

"승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다." 조건에 의해

승객을 찾을 때 연료 체크: F <= info.length 와 승객의 목적지를 찾을 때, 연료 체크: F < fuel가 다르게 된다.

이제 findPeople을 구현해보자.

먼저 tmpMAP에 MAP을 복사한다. 그리고 거리를 재기 위해 visit 배열을 이용한다.

(토마토 문제에서는 MAP에 거리를 바로 쟀지만, 여기에서는 MAP에 승객의 번호를 표시하므로, visit을 따로 둔다.)

tmpMAP에 승객의 번호를 표시할 때,

"승객의 출발지는 모두 다르지만, A 승객의 도착지와 B 승객의 출발지가 같을 수 있다." 조건에 걸리는 경우,

즉시, 승객의 번호와 거리 0을 return 한다.

그리고 BFS로 가장 가까운 승객을 찾는다. 네 방향 탐색을 위해 dr, dc 배열을 이용한다.

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
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 == taxi.r && people[i].sc == taxi.c) return { i, 0 };
	}

	rp = wp = 0;

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

	visit[taxi.r][taxi.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 };
}

tmpMAP[nr][nc]에 사람이 있는 경우에 현재까지 저장된 거리, row, col등을 비교하여 다음에 태울 승객을 갱신한다.

"현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다." 조건에 의해 if문이 복잡해진다.

목적지로 이동하는 함수는 단순히 거리만 재면 된다.

도달할 수 없는 목적지의 경우 -1을 return한다.

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 = taxi.r;
	queue[wp++].c = taxi.c;

	visit[taxi.r][taxi.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;
}

findPeople, goToDestination 둘 다 거리를 넘겨줄 때는 -1을 빼서 return해야 한다.

visit에 check할 때, 현재의 위치를 1로 두고 시작하기 때문이다.

최종 코드는 아래를 참고하자.

#include <stdio.h>

#define MAX (20 + 5)

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

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

RC taxi;
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", &taxi.r, &taxi.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 == taxi.r && people[i].sc == taxi.c) return { i, 0 };
	}

	rp = wp = 0;

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

	visit[taxi.r][taxi.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 = taxi.r;
	queue[wp++].c = taxi.c;

	visit[taxi.r][taxi.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;

		taxi.r = people[peopleNumber].sr; /* 택시 이동 */
		taxi.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배 증가 */

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

	return F;
}

int main(void)
{
	input();

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

	return 0;
}

실제 A형의 tc는 여러 개이므로 people의 check를 모두 0으로 초기화하는 코드가 필요하다.

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

BOJ 20056 : 마법사 상어와 파이어볼 (삼성 SW TEST A형) (0)	2021.04.13
BOJ 20055 : 컨베이어 벨트 위의 로봇 (삼성 SW TEST A형) (0)	2021.04.10
BOJ 19237 : 어른 상어 (삼성 SW TEST A형) (0)	2021.04.06
BOJ 19236 : 청소년 상어 (삼성 SW TEST A형) (0)	2021.04.03
BOJ 20061 : 모노미노도미노 2 (삼성 SW TEST A형) (0)	2021.03.31

피로물든딸기의 라이브러리

BOJ 19238 : 스타트 택시 (삼성 SW TEST A형)

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

댓글

티스토리툴바

BOJ 19238 : 스타트 택시 (삼성 SW TEST A형)

A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기)

'알고리즘 > [ADV] 삼성 SW 역량 테스트 A형' 카테고리의 다른 글

관련글

댓글

티스토리툴바