[백준] 16118번: 달빛 여우

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

16118번: 달빛 여우

---

1. 문제 조건

1) 그루터기 $N$ 개와 양방향 오솔길 $M$ 개가 주어진다.

2) 여우와 늑대는 1번 그루터기에 있다.

3) 여우는 항상 같은 속도로 이동한다.

4) 늑대는 처음에는 여우의 2배 속도로, 다음에는 여우의 절반 속도로 이동한다.

5) 여우가 늑대보다 더 먼저 도착할 수 있는 그루터기의 개수를 출력한다.

 

2. 문제 풀이

상당히 신박한 문제였다.

다익스트라 알고리즘을 이용해서 풀어보자.

 

이 문제에는 당황스러운 부분이 2가지 있는데, 현명하게 해결해야 한다.

 

1) 여우와 늑대의 속도가 주어지지 않는다.

- 문제에서 요구하는 것이 최단 시간이 아니다.

- 여우와 늑대의 상대 속도로 생각하자.

- 즉, 오솔길의 길이로만 문제를 풀어도 된다.

 

2) 늑대가 이동한 최단 시간이 소수가 될 수도 있다.

- 소수로 최단 시간을 구하면, 정확도에서 문제가 생길수도 있다.

- 최대한 소수를 피해 정수로 문제를 풀어야 한다.

- 여우와 늑대의 속도는 상대적이고 여우의 속도가 기준이다.

- 여우의 속도를 2라고 하면, 늑대의 달리기 속도는 4, 걷기 속도는 1이 된다.

- 따라서 주어지는 오솔길의 길이를 2배로 해서 그래프를 구성하면 쉽게 해결된다.

 

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

현재 노드에 도달할 때 달렸는지 여부도 저장하도록 하였다.

여우와 늑대의 Node 배열을 따로 선언했는데

늑대는 같은 노드라도 달려서 왔는지 걸어서 왔는지 따로 저장하도록 배열을 선언하였다.

#define MAXN 4001

#define NONE -1
#define RUN   0
#define WALK  1

struct Node
{
	int ID;			// 노드 번호
	ll dist;		// 이 노드까지의 최단 시간
	int state;		// 이 노드로 왔을 때 달렸으면 0, 걸었으면 1 / default -1
	int heapIdx;	// heap 안에서의 index
	bool inHeap;	// heap 안에 있는지 여부

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

Node nodeF[MAXN];		// 여우에 관한 경우
Node nodeW[MAXN][2];	// 늑대에 관한 경우

 

이제 모든 준비가 끝났다.

먼저 여우에 대해 전형적인 다익스트라 알고리즘을 돌려준다.

1번 노드에서 시작해서 모든 노드의 최단 시간을 계산해주면 된다.

 

다음으로 늑대에 대해 다익스트라를 돌려준다.

처음에는 달리기로 시작해야 하므로,

nodeW[1][WALK] 를 heap 에 넣고 시작한다.

그래야 다음 노드로 RUN 할 수 있기 때문이다.

참고로, 다음 상태는 현재 상태에 1을 xor 해주면 쉽게 toggle 할 수 있다.

 

다음 상태가 RUN 이라면, 오솔길의 길이를 2로 나누어서 사용하고

다음 상태가 WALK 라면, 오솔길의 길이를 2배 해서 사용하면 된다.

 

다익스트라 알고리즘이 모두 끝났다면

모든 노드에 대해 여우의 최단 시간이 늑대보다 작은 노드의 개수를 세서 출력하면 된다.

---

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

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

#define MAXN 4001

#define NONE -1
#define RUN   0
#define WALK  1

typedef long long ll;

const ll INF = 1e16;

struct Edge {int e, w; };

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

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

struct Heap
{
	Node* data[MAXN<<1];
	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 nodeF[MAXN];
Node nodeW[MAXN][2];
Heap heap;

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

	int N, M; cin >> N >> M;
	int a, b, d;
	while(M--)
	{
		cin >> a >> b >> d;

		graph[a].push_back({b, d<<1});
		graph[b].push_back({a, d<<1});
	}

	for(int i=1; i<=N; i++)
	{
		nodeF[i].init(i);
		nodeW[i][RUN].init(i, RUN);
		nodeW[i][WALK].init(i, WALK);
	}

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

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

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

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

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

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

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

		for(Edge edge : graph[ID])
		{
			int nID = edge.e;
			int nState = state ^ 1;
			ll nDist = dist + ((nState == RUN) ? (edge.w >> 1) : (edge.w << 1));

			if(nodeW[nID][nState].dist > nDist)
			{
				nodeW[nID][nState].dist = nDist;

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

	int ans = 0;
	for(int i=1; i<=N; i++)
	{
		ll minW = (nodeW[i][RUN].dist < nodeW[i][WALK].dist) ? nodeW[i][RUN].dist : nodeW[i][WALK].dist;

		if(nodeF[i].dist < minW) ans++;
	}

	cout << ans << '\n';

	return 0;
}