[백준] 1162번: 도로포장

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

1162번: 도로포장

---

1. 문제 조건

1) 도시 $N$ 개와 양방향 도로 $M$ 개가 주어진다.

2) 1번 → $N$ 번 도시로 이동해야 한다.

3) $K$ 개 이하의 도로를 포장할 수 있다.

4) 도로를 포장하면 이동 시간이 0 이 된다.

5) $N$ 번 도시까지 도달했을 때의 최단 시간을 출력한다.

 

2. 문제 풀이

dynamic programming 스타일의 다익스트라 알고리즘 문제다.

 

$K$ 개 이하로 도로를 포장해서 이동 시간을 0으로 만들 수 있다는 조건이 문제를 어렵게 만든다.

이 조건 때문에 다익스트라 알고리즘의 그리디 특성이 깨진다.

따라서 도로를 포장한 횟수마다 상태를 저장해서 문제를 해결해야 한다.

 

나는 Node 구조체를 아래와 같이 정의하였다.

같은 노드라도 도로를 포장한 개수에 따라 각각 정보를 유지하도록 했다.

#define MAXN 10001
#define MAXK 21

struct Node
{
	int ID;			// 노드 번호
	ll dist;		// 이 노드까지의 최단 시간
	int k;			// 이 노드까지 도로 포장 횟수
	int heapIdx;	// heap 안에서의 index
	bool inHeap;	// heap 안에 있는지 여부

	void init(int ID, int k)
	{
		this->ID = ID;
		dist = INF;
		this->k = k;
		heapIdx = -1;
		inHeap = false;
	}
};

// node[n][k] = n번 노드까지 도로를 k개 포장한 경우
Node node[MAXN][MAXK];

 

우리가 고려해야 할 사항은 크게 2가지다.

 

1) 다음 노드로의 도로를 포장하지 않는 경우

- 다음 노드의 포장 개수는 현재 노드의 포장 개수와 같다.

- 다음 노드로의 이동 시간은 현재 노드의 최단 시간 + 도로 통과 시간이다.

 

2) 다음 노드로의 도로를 포장하는 경우

- 현재 노드의 포장 개수가 최대 포장 가능 개수 $K$ 보다 작아야 한다.

- 다음 노드의 포장 개수는 현재 노드의 포장 개수 + 1 이다.

- 다음 노드로의 이동 시간은 현재 노드의 최단 시간과 같다.

 

위 2가지 조건을 확인하면서

포장 개수에 알맞는 노드의 정보를 갱신하여 heap 에 넣어주면 된다.

heap 은 최단 시간으로 정렬되기 때문에

$N$ 번 도시가 나오는 즉시 알고리즘을 종료하면 된다.

---

전체 풀이 코드는 다음과 같다.

#include <iostream>
#include <vector>
using namespace std;

#define MAXN 10001
#define MAXK 21

typedef long long ll;

const ll INF = 1e16;

struct Edge {int e, w; };

struct Node
{
	int ID;
	ll dist;
	int k;
	int heapIdx;
	bool inHeap;

	void init(int ID, int k)
	{
		this->ID = ID;
		dist = INF;
		this->k = k;
		heapIdx = -1;
		inHeap = false;
	}
};

struct Heap
{
	Node* data[MAXN*MAXK];
	int size;

	void init() { size = 0; }

	bool isEmpty() { return size == 0; }

	void swap(int a, int b)
	{
		data[a]->heapIdx = b;
		data[b]->heapIdx = a;

		Node *temp = data[a];
		data[a] = data[b];
		data[b] = temp;
	}

	bool compare(int a, int b) { return data[a]->dist < data[b]->dist; }

	int updateUp(int idx)
	{
		while(true)
		{
			if(!idx) break;

			int parent = (idx - 1) >> 1;
			if(compare(parent, idx)) break;

			swap(idx, parent);
			idx = parent;
		}

		return idx;
	}

	void updateDown(int idx)
	{
		while(true)
		{
			int child1 = (idx << 1) + 1;
			int child2 = (idx << 1) + 2;

			if(child1 >= size) break;

			int child = child1;
			if(child2 < size)
			{
				child = compare(child1, child2) ? child1 : child2;
			}

			if(compare(idx, child)) break;

			swap(idx, child);
			idx = child;
		}
	}

	void update(int idx) { updateDown(updateUp(idx)); }

	void push(Node *newNode)
	{
		newNode->heapIdx = size;
		newNode->inHeap = true;

		data[size] = newNode;
		size++;

		updateUp(size-1);
	}

	Node* pop()
	{
		Node *ret = data[0];
		ret->inHeap = false;

		swap(0, size-1);
		size--;

		updateDown(0);

		return ret;
	}
};

vector<Edge> graph[MAXN];

Node node[MAXN][MAXK];
Heap heap;

int N, M, K;

int min(int a, int b) { return a < b ? a : b; }

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> K;
	int u, v, w;
	while(M--)
	{
		cin >> u >> v >> w;
		graph[u].push_back({v, w});
		graph[v].push_back({u, w});
	}

	for(int i=1; i<=N; i++)
	{
		for(int k=0; k<=K; k++) node[i][k].init(i, k);
	}

	heap.init();
	node[1][0].dist = 0;
	heap.push(&node[1][0]);

	ll ans = -1;
	while(!heap.isEmpty())
	{
		Node *curr = heap.pop();
		int ID = curr->ID;
		ll dist = curr->dist;
		int k = curr->k;

		if(ID == N)
		{
			ans = dist;
			break;
		}

		for(Edge edge : graph[ID])
		{
			int nID = edge.e;
			int nk = k;
			ll nDist = dist + edge.w;

			if(node[nID][nk].dist > nDist)
			{
				node[nID][nk].dist = nDist;

				if(node[nID][nk].inHeap) heap.update(node[nID][nk].heapIdx);
				else					 heap.push(&node[nID][nk]);
			}

			if(k < K)
			{
				nk++; nDist -= edge.w;

				if(node[nID][nk].dist > nDist)
				{
					node[nID][nk].dist = nDist;

					if(node[nID][nk].inHeap) heap.update(node[nID][nk].heapIdx);
					else					 heap.push(&node[nID][nk]);
				}
			}
		}
	}
	
	cout << ans << '\n';

	return 0;
}