백준 19238 - 스타트 택시(골드4)

문제

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

긴 지문에 고통스러운 구현문제이다.

접근법

가장 가까운 손님을 태우는 것, 손님을 목적지로 배달하는 것, 둘 다 bfs로 생각했다.

가장 가까운 손님을 태우는 것은 bfs를 돌면서 손님이 있으면 다 벡터에 넣어서, 조건대로 정렬 후 가장 앞에 있는 원소를 선택하는 방식으로 구현했다.

손님을 배달하는 것도 bfs를 돌아 배달시켰다.

중간에 연료가 떨어지거나, 태울 손님이 없거나 하는 부분은 좀 무식하게 구현한 감이 없지않아 있어서, 더 나은 방법을 찾아봐야겠다.

벽이 없는 경우의 최단거리는 좌표값 차이로 구할 수 있고, 벽이 있는 경우의 최단거리는 bfs를 통해 구한다는 것을 깨닫는 계기가 되었다.

구현

#include <stdio.h>
#include <queue>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef struct __t
{
	int row;
	int col;
	int sec;
	int gas;
}Taxi;

int n,m,gas;
int r,c;
int ans=-1;
int map[21][21];
int visit[21][21];
pair<int,int> cache[21][21];
Taxi taxi;
int dy[4]={0,0,-1,1};
int dx[4]={-1,1,0,0};
int done=0;
int die=0;
bool cmp(const Taxi& x,const Taxi& y)
{
	if(x.row==y.row && x.sec==y.sec)
		return x.col<y.col;
	if(x.sec==y.sec)
		return x.row<y.row;
	
	return x.sec<y.sec;
}
void findsonnim()
{
	queue<Taxi> q;
	vector<Taxi> v;
	
	memset(visit,0,sizeof(visit));
	q.push(taxi);
	visit[taxi.row][taxi.col]=1;
	while(!q.empty())
	{
		Taxi pp=q.front();
		q.pop();
		
		if(map[pp.row][pp.col]==2)
		{
			v.push_back(pp);
		}
		if(pp.gas<=0)
		{
			continue;
		}
		for(int i=0;i<4;i++)
		{
			int R=pp.row+dy[i];
			int C=pp.col+dx[i];
			if(R<1 || R>n || C<1 || C>n ||map[R][C]==1 || visit[R][C])
				continue;
			
			Taxi np;
			np.row=R;
			np.col=C;
			np.sec=pp.sec+1;
			np.gas=pp.gas-1;
			q.push(np);
			visit[R][C]=1;
			
			
		}
	}
	if(!v.empty())
	{
	
		sort(v.begin(),v.end(),cmp);
		taxi=v[0];
		taxi.sec=0;
		map[v[0].row][v[0].col]=0;
		done=0;
	}
	else
	{
		int flag=1;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(map[i][j]==2)
				{
					flag=0;
					break;
				}
			}
			if(!flag)
				break;
		}
		
		if(flag==0)
			done=2;
		else
		 	done=1;
	}

}
void move()
{
	queue<Taxi> q;
	memset(visit,0,sizeof(visit));
	q.push(taxi);
	visit[taxi.row][taxi.col]=1;
	while(!q.empty())
	{
		Taxi pp=q.front();
		q.pop();
		
		if(pp.row==cache[taxi.row][taxi.col].first && pp.col==cache[taxi.row][taxi.col].second)
		{
			taxi.row=pp.row;
			taxi.col=pp.col;
			taxi.gas=pp.gas+pp.sec*2;
			taxi.sec=0;
			return;
		}
		
		if(pp.gas<=0)
		{
			continue;
		}
		
		for(int i=0;i<4;i++)
		{
			int R=pp.row+dy[i];
			int C=pp.col+dx[i];
			
			if(R<1 || R>n || C<1 || C>n || map[R][C]==1 || visit[R][C])
				continue;
				
			Taxi np;
			np.row=R;
			np.col=C;
			np.sec=pp.sec+1;
			np.gas=pp.gas-1;
			q.push(np);
			visit[R][C]=1;
		}
	}
	
	
	die=1;
	
}
int main()
{
	scanf("%d %d %d",&n,&m,&gas);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			scanf("%d",&map[i][j]);
		}
	}
	memset(cache,0,sizeof(cache));
	scanf("%d %d",&r,&c);
	taxi.row=r;
	taxi.col=c;
	taxi.sec=0;
	taxi.gas=gas;
	
	for(int i=0;i<m;i++)
	{
		int sr,sc,er,ec;
		scanf("%d %d %d %d",&sr,&sc,&er,&ec);
		map[sr][sc]=2;
		cache[sr][sc]=make_pair(er,ec);
	}
	
	while(1)
	{
		findsonnim();

		if(done==1)
		{
			printf("%d",taxi.gas);
			break;
		}
		else if(done==2)
		{
			printf("-1\n");
			break;
		}
		move();
		if(die)
		{
			printf("-1\n");
			break;
		}
	
	}
	return 0;
}