[백준 10043] 택시

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

10043번: タクシー (Taxis)

// BFS로 해결 
#include <cstdio>
#include <queue>
#include <algorithm>
#include <list>	
int N, K;
int chk[5000 + 2][5000 + 2];	// 상태발전을 위한 체크배열

struct _st
{
	int n;
	int cnt;
	int cost;
};


struct _tx
{
	int cost;
	int cnt;
}taxi[5000 + 2];

using namespace std;

list<int> adj[5000 + 2];		// 연결된 마을 인접리스트로 표현


struct COMP
{
	bool operator() (_st &a, _st &b)
	{
		return a.cost > b.cost;		// cost를 기준으로 내림차순 정렬한다.	// 그래야 cost 작은 것 부터 나옴 
	}

};
priority_queue<_st, vector<_st>, COMP> PQ;	// 최소 비용 구하기 위해

void input(void)
{
	scanf("%d %d", &N, &K);
	for (int i = 1; i <= N; i++) {
		scanf("%d %d", &taxi[i].cost, &taxi[i].cnt);
	}
	for (int i = 0; i < K; i++) {
		int u = 0; int v = 0;
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}



int BFS(void)
{
	fill(&chk[0][0], &chk[0][0] + sizeof(chk) / sizeof(int), 0x7fffffff);	// 방문배열 초기화 

	PQ.push({ 1, 0, 0 });	// 1번 회사에서 이동 횟수가 0번 남은 택시를 탐, 총비용 0원
	chk[1][0] = 0;			// [회사][남은 이동 횟수] = 총비용 

	while (!PQ.empty()) {
		_st data = PQ.top();
		PQ.pop();

		if (data.n == N) return data.cost;


		int next = 0; int ncnt = 0; int ncost = 0;
		if (data.cnt != 0) {	// 이동 횟수가 남아있다면
			ncnt = data.cnt - 1;	// 이동횟수 차감 
			ncost = data.cost;		// 안갈아탐		// 비용증가없음 

			for (int nn : adj[data.n]) {
				next = nn;
				if (chk[next][ncnt] <= ncost) continue;
				chk[next][ncnt] = ncost;
				PQ.push({ next, ncnt, ncost });
			}
		}

		ncnt = taxi[data.n].cnt - 1;
		ncost = data.cost + taxi[data.n].cost;	// data.n번째에서 택시 갈아타니까
		for (int nn : adj[data.n]) {
			next = nn;
			if (chk[next][ncnt] <= ncost) continue;
			chk[next][ncnt] = ncost;
			PQ.push({ next, ncnt, ncost });
		}
	}
}


int main()
{
	input();
	int ans = BFS();
	printf("%d\n", ans);
	return 0;
}

ㅇ... 일본어.... 고멘나사이... 

 

문제 설명을 대충하자면, 1번 노드에서부터 N번 노드까지 가기 위해 필요한 최소 비용을 구하는 문제이다. 

각 노드는 K개의 도로로 연결되어 있고, 양방향으로 자유롭게 움직일 수 있다. 

한편 다음과 같은 조건을 따른다. 

1. i번 택시 회사의 택시는 i번 마을에서만 승차할 수 있다. 

2. i번 택시 회사의 택시 요금은 이용한 거리에 관계없이 Ci이다.

3. i번 택시 회사의 택시는 승차 후 연속 최대 Ri개의 도로밖에 갈 수 없다. 

 

 

// input( ) 함수 

각 택시의 요금와 이동할 수 있는 도로 수를 구조체에 받아주었고, 연결된 두 노드를 표시하기 위해 리스트를 만들어 놓았다. 또한 양방향으로 자유롭게 이동할 수 있기 때문에 u에도 v를, v에도 u를 추가하였다. 

 

 

// BFS( ) 함수

노드 N에 도달했을 때 최소 비용을 리턴하기 위해 "우선순위 큐"를 선언하였다. 

가장 처음 큐에 담아준 데이터는 1번 노드에서 이동 횟수가 0번 남은 택시를 탔고, 총 비용이 0원인 상태이다. 

그리고 행번호가 노드, 열번호가 이동횟수인 chk배열의 chk[1][0]에 1번 노드까지 오는데 이동횟수가 0번 남았을 때의 총비용인 0을 대입해준다. 

 

이후 PQ에서 데이터를 하나씩 꺼내어 상태를 발전시키는데, 만약 꺼낸 데이터의 노드가 N이라면 그때까지의 총 비용(data.sum)을 리턴해주고 종료한다. 

그게 아니라면 루프를 계속 진행하는데,

(1) 만약 이동횟수가 아직 남아있다면( if (data.cnt != 0)) 이동 횟수를 차감한다(ncnt = data.cnt - 1). 한편 택시를 갈아타지 않았 기 때문에 비용이 증가하지는 않는다. 따라서 총 비용은 그대로이다(nsum = data.sum).

(2) 반면 이동횟수가 더이상 남아있지 않다면, 해당 노드에서 새로운 택시로 갈아타고 이동해야 한다. 따라서 새로운 택시를 타야하고, 다음 노드로 이동할 것이므로 이동횟수 -1 을 해준다(ncnt = taxi[data.n].cnt - 1). 또한 총 비용은 지금까지의 금액에 새로운 택시를 탔을 때 발생하는 비용을 더해주어야 한다. (ncost = data.cost + taxi[data.n].cost)   

 

상기 두 경우 chk배열에서 해당 노드(next)에서 이동횟수가 ncnt개 남았을 때 발생하였던 비용과 새로 계산한 ncost를 비교하여, 새로 계산한 비용이 더 작을 때만 chk 배열을 갱신 후 정보를 우선순위 큐에 삽입한다.