백준 19238 스타트 택시 C풀이 - BFS

스마트하고 그리디한 택시기사를 위한 문제이다.

 

문제의 조건은 다음과 같다.

1. 가장 가까운 승객을 태운다.(여러명일 경우 y가 가장 작은 승객, y가 같은 경우 x가 가장 작은 승객을 먼저 태운다)

2. 승객을 목적지 까지 태워준다.

3. 연료는 1칸 이동할때마다 1씩 닳는다.

4-1. 승객에 도착하기 전 연료가 다하거나 목적지에 도착하기 전 연료가 다하면 -1을 출력한다.

4-2. 승객을 모두 태우기 전에 종료되면 -1을 출력한다.

5. 도착지에 도착하면, 승객을 태운 위치에서부터 걸린 시간(이동한 칸 수)의 2배만큼의 연료를 충전한다.

6. 모두 태우고 나서 남은 연료의 양을 출력한다.

7. 벽은 지나가지 못한다.

 

문제의 접근 방식 및 해결방식은 다음과 같다.

1. 가장 가까운 승객을 찾는다.(BFS)

2. 목적지까지 최단경로를 찾는다.(BFS)

3. 연료를 중간중간 확인한다.

4. 승객이 있는 위치는 Map에 음수로 표현한다.(인덱스의 음수)

 

고생한 점은 다음과 같다.

1. 태운 승객 정보 지우기 - 함수 인덱스로 넣기 전에 지워버려서 문제가 생겼었다.

 

최적화 방식은 다음과 같다.

1. 메모리 - 같은 큐를 사용하여 N*N 정도의 크기만큼만 운영했다.

2. 수행시간 - visit 배열을 태운 승객 수로 기록하여 초기화 시간을 줄였다.(M* N^2 감소);

3. 승객의 도착지점 정보를 인덱스로 O(1)로 접근하여 탐색시간을 줄였다.

 

만약 실행하자마자 틀린다면 (0% 나 1%) 택시의 출발지점에 손님이 있는 경우를 고려하지 않았을 가능성이 크다.

 

 

전체코드

#include <stdio.h>

#define DEBUG 0
#define MAX_N 20
#define MAX_M (20*20)
int N, M, S_oil;
int sy, sx;
int Map[MAX_N+2][MAX_N+2];
int f_visited[MAX_N + 2][MAX_N + 2];//손님 찾는 배열
int g_visited[MAX_N + 2][MAX_N + 2];//도착점 찾는 배열
typedef struct s {
	int y, x, dy, dx;
}CUSTOMER;
CUSTOMER Customer[MAX_M + 2];//손님의 위치와 목적지
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0, -1 ,1 };

typedef struct st {
	int y, x, mv;
}QUEUE;
QUEUE queue[MAX_M +10];//큐
int wp, rp;
void pop() { rp++; }
void push(QUEUE x) { queue[wp++] = x; }
int empty() { return wp == rp; }
QUEUE front() { return queue[rp]; }

//승객 찾기
QUEUE find(int idx) {
	wp = rp = 0;
	QUEUE ret = { 21,21,21 };
	int stop = 20*20+1;
	QUEUE cur = { sy,sx,0 };
	//승객이 시작지점에 있을 경우(음수)
	if (Map[sy][sx] < 0) {
		ret.y = sy;
		ret.x = sx;
		ret.mv = 0;
	}
	else {
		push(cur);
	}
	while (!empty()) {
		cur = front(); pop();
		//연료보다 많이 이동할 경우 (같을 경우면 이미 찾았어야하는데 못찾은 경우임)
		if (S_oil - cur.mv <= 0) break;
		//가장 가까운 승객을 찾았는데 같은 거리의 다른 승객이 있는지를 찾기 위해
		//stop을 설정해두고 더 먼 거리로 진행하지 않도록break
		if (stop <= cur.mv) break;
		for (int i = 0; i < 4; i++) {
			int ny = cur.y + dy[i];
			int nx = cur.x + dx[i];
			if (ny > N || ny <= 0 || nx > N || nx <= 0) continue;
			//벽
			if (Map[ny][nx] == 1) continue;
			//같은 과정에서 이미 들렀다면
			if (f_visited[ny][nx] == idx) continue;
			f_visited[ny][nx] = idx;
			//승객을 찾은경우
			if (Map[ny][nx] < 0) {
				//y가 가장 작은 것 저장
				if (ret.y > ny) {
					ret.y = ny;
					ret.x = nx;
					ret.mv = cur.mv + 1;
					stop = cur.mv + 1;
				}
				//같은 경우 x가가장 작은 것 저장
				else if (ret.y == ny) {
					if (ret.x > nx) {
						ret.y = ny;
						ret.x = nx;
					}
				}
			}
			QUEUE tmp = { ny,nx, cur.mv + 1 };
			push(tmp);
		}
		
	}
	//연료 빼줌
	S_oil -= ret.mv;
	//빠져나가서 연료가 음수면 즉시 종료
	return ret;
}

//목적지까지 찾기, 승객 정보, 승객 정보 인덱스(customer의 인덱스), 태운 승객수
int go(QUEUE next_Customer, int idx, int num){
	//큐 초기화
	wp = rp = 0;
	//위 함수에서 구한 승객정보 넣기
	QUEUE cur = next_Customer;
	//승객이 있는 위치 0으로 초기화
	Map[cur.y][cur.x] = 0;
	cur.mv = 0;
	push(cur);
	while (!empty()) {
		cur = front(); pop();
		//연료 다할경우
		if (S_oil - cur.mv <=0) break;
		for (int i = 0; i < 4; i++) {
			int ny = cur.y + dy[i];
			int nx = cur.x + dx[i];
			if (ny >N || ny <= 0 || nx > N || nx <= 0) continue;
			if (Map[ny][nx] == 1) continue;
			if (g_visited[ny][nx] == num) continue;
			g_visited[ny][nx] = num;
			//목적지에 도착한경우
			if (ny == Customer[idx].dy && nx == Customer[idx].dx) {
				S_oil -= cur.mv+1;
				//못도착할 경우
				if (S_oil < 0) return -1;
				//연료충전
				S_oil += 2 * (cur.mv + 1);
				//택시위치 수정
				sy = ny;
				sx = nx;
				return 1;
			}
			QUEUE tmp = { ny,nx,cur.mv + 1 };
			push(tmp);
		}
	}
	return -1;
}

int solve() {

	for (int i = 1; i <= M; i++) {
		//가장 가까운 승객 찾기
		f_visited[sy][sx] = i;
		QUEUE next_Customer = find(i);
		//택시위치 수정
		sy = next_Customer.y;
		sx = next_Customer.x;
		//승객 위치까지 도착 못하거나 연료 다쓸경우
		if (S_oil < 0) return -1;
		//목적지 길찾기
		g_visited[next_Customer.y][next_Customer.x] = i;
		int r=go(next_Customer, -(Map[next_Customer.y][next_Customer.x]),i);
		if (r == -1) return -1;

		//반복
	}
	return S_oil;
}

int main() {
	scanf("%d %d %d", &N, &M, &S_oil);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &Map[i][j]);
		}
	}
	scanf("%d %d", &sy, &sx);
	for (int i = 1; i <= M; i++) {
		scanf("%d %d %d %d", &Customer[i].y, &Customer[i].x, &Customer[i].dy, &Customer[i].dx);
		Map[Customer[i].y][Customer[i].x] = -i;
	}

	int ans = solve();
	printf("%d\n", ans);
}