다익스트라 알고리즘(2)

https://www.acmicpc.net/problem/1753
이를 다익스트라 알고리즘을 통해 풀어볼 것이다.

이 문제를 풀기 위해 필요한 것은

1. 그래프 -> 정점이 20000개이므로 $20000^2$개의 성분이 필요한 인접행렬 방식 보다는 인접리스트 방식으로 그래프를 작성

자료형은 struct edge로 필요한 필드는 u, v, weight

2. 최단 거리 배열 -> 1차원 배열이면 충분, 매번 갱신해야 한다

int형 배열이면 충분

3. 우선 순위 큐 -> 가장 가까운 정점이 노드에 있어야 하는데 계속 해서 최단 거리가 갱신된다.

struct node 배열로 필요한 성분은 정점의 번호인 int number와 현재 거리인 int distance

4. visited배열 -> 방문한 적이 있으면 1, 아니면 0
   우선 순위 큐에서 정점을 꺼냈을 때, 방문한 적이 있으면 갱신 함수 실행 X,
   방문한 적 없으면 갱신 함수 실행 O

5. 갱신 함수
   그래프의 정점 번호를 받아와서 visited배열, 최단 거리 배열을 갱신
   갱신한 최단거리를 우선순위 큐에 넣어야 함.

고민거리
우선순위 큐에 들어간 정점1의 최단거리가 10인데 최단거리가 8로 갱신되면 어떻게 최단거리 10짜리를 찾아서 삭제하지?

솔루션 - 찾아서 삭제할 필요가 없다. 어차피 8짜리가 먼저 검색될 것이고 10짜리는 나오면 visited이므로 갱신함수가 실행되지 않는다.

-> 우선 순위 큐가 필요한 이유:
우선 순위 큐를 쓰지 않으면 시간복잡도가 $O(V^2 + E)$이므로 시간 초과가 날 것이다.
(연산이 약 4억번 이상)

우선 순위 큐를 쓰면 시간복잡도가 $O(VlogV + E)$이므로 가능
(연산이 대락 60만회 이상, 단, 우선 순위 큐에 들어가는 갱신되지 않은 최단거리를 가진 정점들은 E에 비례하므로 실재로는 대략 90만회가 될 것)

[소스 코드]

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define INF 100000000

typedef struct edge
{
	int v;
	int weight;

	struct edge* next;
}Edge;

Edge* graph[20001];  // graph 헤드 -> 연결리스트 형식으로 그래프를 구성할 것

int minDistance[20001];

int visited[20001];

typedef struct node
{
	int number;
	int distance;
}Node;

Node heap[300000];
int curHeapNumber;  // 전역변수는 처음에는 0으로 초기화

void insertHeap(Node data)
{
	curHeapNumber++;
	int cur = curHeapNumber;
	int dataDistance = data.distance;

	while (cur/2)
	{
		if (heap[cur / 2].distance > dataDistance)
		{
			heap[cur] = heap[cur / 2];
			cur = cur / 2;
		}

		else
		{
			heap[cur] = data;
			return;
		}
	}

	heap[1] = data;
	return;
}

Node popHeap()
{
	int cur = 1;
	Node temp = heap[1];
	int min;
	int minIndex;

	while (2 * cur + 1 <= curHeapNumber)
	{
		minIndex = heap[2 * cur].distance < heap[2 * cur + 1].distance ? 2 * cur : (2 * cur + 1);
		min = heap[minIndex].distance;

		if (min < heap[curHeapNumber].distance)
		{
			heap[cur] = heap[minIndex];
			cur = minIndex;
		}

		else
		{
			heap[cur] = heap[curHeapNumber];
			break;
		}
	}

	if (2 * cur + 1 > curHeapNumber) heap[cur] = heap[curHeapNumber];

	curHeapNumber--;

	return temp;
}

void relax(int node)
{
	visited[node] = 1;

	Edge* cur = graph[node]->next;
	Node temp;

	while (cur)
	{
		if (cur->weight + minDistance[node] < minDistance[cur->v])
		{
			minDistance[cur->v] = cur->weight + minDistance[node];
			temp.number = cur->v;
			temp.distance = minDistance[cur->v];

			insertHeap(temp);  // 어차피 이렇게 넣어도 이전에 들어갔던 최단거리가 갱신 안 된 노드는 visited이기 때문에 영향 주지 X
		}

		cur = cur->next;
	}

	return;
}


int main()
{
	int i, V, E, K;  // 각각 정점의 개수, 간선의 개수, 시작 정점의 번호
	scanf("%d %d %d", &V, &E, &K);

	Edge* cur[20001];

	for (i = 1; i <= V; i++)
	{
		graph[i] = malloc(sizeof(Node));
		graph[i]->next = NULL;
		cur[i] = graph[i];
		minDistance[i] = INF;
	}

	minDistance[K] = 0;

	int u, v, w;

	for (i = 0; i < E; i++)
	{
		scanf("%d %d %d", &u, &v, &w);
		cur[u]->next = malloc(sizeof(Edge));

		cur[u] = cur[u]->next;

		cur[u]->v = v;
		cur[u]->weight = w;
		cur[u]->next = NULL;
	}

	Node temp;
	temp.number = K;
	temp.distance = 0;

	insertHeap(temp);

	while (curHeapNumber)
	{
		temp = popHeap();

		/*printf("popHeap: [%d %d]\n", temp.number, temp.distance);

		printf("minDistance: ");*/

		//for (i = 1; i <= V; i++)  // 디버깅용
		//{
		//	if (minDistance[i] == INF) printf("INF ");
		//	else printf("%d ", minDistance[i]);
		//}

		//printf("\n");

		//printf("curHeapNumber: %d\n", curHeapNumber);

		//printf("Heap: ");

		//for (i = 1; i <= curHeapNumber; i++)
		//{
		//	printf("[%d %d]", heap[i].number, heap[i].distance);
		//}

		//printf("\n");

		if (!visited[temp.number])
		{
			relax(temp.number);
		}

		else continue;
	}

	for (i = 1; i <= V; i++)
	{
		if (minDistance[i] == INF) printf("INF\n");
		else printf("%d\n", minDistance[i]);
	}
	return 0;
}

Tip.

graph[]와 같이 head로 쓰는 배열들은 당연하게도 next를 모두 NULL로 초기화해주어야한다.