BOJ 11779 : 최소비용 구하기 2

알고리즘 문제 전체 링크

 

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

 

※ 다익스트라를 이용하여 최단 경로 이동하기는 유니티에서 확인할 수 있다.

 

출발 도시에서 도착 도시까지 가는데 드는 최소 비용과 도시의 개수 그리고 최소 비용이 되는 경로도 출력해야 한다.

 

메모리 풀 방식으로 각 도시 간의 연결과 가중치를 저장한다.

typedef struct st
{
	int value;
	int weight;
	struct st *next;
}NODE;

NODE HEAD[1010];
NODE POOL[100100];
int pcnt;

void Make(int p, int c, int w)
{
	NODE *nd = &POOL[pcnt++];

	nd->value = c;
	nd->weight = w;

	nd->next = HEAD[p].next;
	HEAD[p].next = nd;
}

 

다익스트라(데이크스트라) 알고리즘을 위해 최소 힙을 만든다.

typedef struct st2
{
	int node;
	int weight;
}EDGE;

EDGE heap[300010];
int hn;

EDGE pop(EDGE* heap, int& hn)
{
	EDGE ret, tmp;

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn--].weight = 0x7fff0000;

	for (int i = 1; i * 2 <= hn;)
	{
		if (heap[i].weight < heap[i * 2].weight && heap[i].weight < heap[i * 2 + 1].weight) break;
		if (heap[i * 2].weight < heap[i * 2 + 1].weight)
		{
			tmp = heap[i];
			heap[i] = heap[i * 2];
			heap[i * 2] = tmp;

			i = i * 2;
		}
		else
		{
			tmp = heap[i];
			heap[i] = heap[i * 2 + 1];
			heap[i * 2 + 1] = tmp;

			i = i * 2 + 1;
		}
	}

	return ret;
}

void push(EDGE* heap, int& hn, EDGE x)
{
	EDGE tmp;
	heap[++hn] = x;
	
	for (int i = hn; i > 1; i /= 2)
	{
		if (heap[i / 2].weight < heap[i].weight) break;
		
		tmp = heap[i / 2];
		heap[i / 2] = heap[i];
		heap[i] = tmp;
	}
}

 

distance[i]는 start를 기준으로 i 도시 까지 걸리는 최소 비용이다.

그리고 방문 여부를 표시하는 visit 배열과 최소 거리에서 어느 도시에서 왔는지 저장할 from 배열을 선언한다.

int distance[1010];
int visit[1010];
int from[1010];

---

먼저 main에서 각 도시에 대해 그래프를 만든다. 

int main()
{
	int u, v, w;
	
	scanf("%d %d", &N, &M);

	for (int i = 0; i < M; i++)
	{
		scanf("%d %d %d", &u, &v, &w);
		Make(u, v, w);
	}

	scanf("%d %d", &start, &end);
    
    ...
}

 

다익스트라로 최솟값을 갱신하기 위해서 모든 거리를 무한대 정한다.

출발점과 출발점의 거리는 0이기 때문에 0으로 두고 heap에 넣는다.

	for (int i = 1; i <= N; i++) distance[i] = 0x7fff0000;

	distance[start] = 0;

	push(heap, hn, { start, 0 });

 

다익스트라는 방문하지 않은 도시 중에서 비용이 가장 작은 도시를 꺼낸 후, 연결된 도시를 체크하여 비용을 갱신한다.

	while (hn)
	{
		NODE *nd;
		EDGE tmp;

		tmp = pop(heap, hn); // 가장 비용이 작은 도시 

		if (visit[tmp.node]) continue; 중 선택되지 않은 도시

		visit[tmp.node] = 1; 

		for (nd = HEAD[tmp.node].next; nd; nd = nd->next) // 모든 도시 체크
		{
            // (현재 비용)보다 
            // (지금까지 든 비용 + 다음 도시 비용)이 적은 경우 갱신
			if (distance[nd->value] > distance[tmp.node] + nd->weight)
			{
				from[nd->value] = tmp.node;
				distance[nd->value] = distance[tmp.node] + nd->weight;
				push(heap, hn, { nd->value, distance[nd->value] });
			}
		}
	}

 

모든 도시에 대해 비용이 정해졌고, from에는 각 도시가 최소 비용으로 도착하기 바로 전 도시가 저장되어 있다.

재귀 함수를 이용해 start → end로 가면서 방문한 도시를 역으로 출력한다.

void DFS(int L, int ed)
{
	if (from[ed] == 0)
	{
		printf("%d\n", L);
		printf("%d ", ed);
		return;
	}

	DFS(L + 1, from[ed]);
	printf("%d ", ed);

}

int main()
{
	...

	printf("%d\n", distance[end]);
	
	DFS(1, end);

	putchar('\n');

	return 0;
}

 

최종 코드는 아래와 같다.

#include <stdio.h>

int N, M;
int start, end;

typedef struct st
{
	int value;
	int weight;
	struct st *next;
}NODE;

NODE HEAD[1010];
NODE POOL[100100];
int pcnt;

void Make(int p, int c, int w)
{
	NODE *nd = &POOL[pcnt++];

	nd->value = c;
	nd->weight = w;

	nd->next = HEAD[p].next;
	HEAD[p].next = nd;
}

int distance[1010];
int visit[1010];
int from[1010];

typedef struct st2
{
	int node;
	int weight;
}EDGE;

EDGE heap[300010];
int hn;

EDGE pop(EDGE* heap, int& hn)
{
	EDGE ret, tmp;

	ret = heap[1];
	heap[1] = heap[hn];
	heap[hn--].weight = 0x7fff0000;

	for (int i = 1; i * 2 <= hn;)
	{
		if (heap[i].weight < heap[i * 2].weight && heap[i].weight < heap[i * 2 + 1].weight) break;
		if (heap[i * 2].weight < heap[i * 2 + 1].weight)
		{
			tmp = heap[i];
			heap[i] = heap[i * 2];
			heap[i * 2] = tmp;

			i = i * 2;
		}
		else
		{
			tmp = heap[i];
			heap[i] = heap[i * 2 + 1];
			heap[i * 2 + 1] = tmp;

			i = i * 2 + 1;
		}
	}

	return ret;
}

void push(EDGE* heap, int& hn, EDGE x)
{
	EDGE tmp;
	heap[++hn] = x;
	
	for (int i = hn; i > 1; i /= 2)
	{
		if (heap[i / 2].weight < heap[i].weight) break;
		
		tmp = heap[i / 2];
		heap[i / 2] = heap[i];
		heap[i] = tmp;
	}
}

void DFS(int L, int ed)
{
	if (from[ed] == 0)
	{
		printf("%d\n", L);
		printf("%d ", ed);
		return;
	}

	DFS(L + 1, from[ed]);
	printf("%d ", ed);

}

int main()
{
	int u, v, w;
	
	scanf("%d %d", &N, &M);

	for (int i = 0; i < M; i++)
	{
		scanf("%d %d %d", &u, &v, &w);
		Make(u, v, w);
	}

	scanf("%d %d", &start, &end);

	for (int i = 1; i <= N; i++) distance[i] = 0x7fff0000;

	distance[start] = 0;

	push(heap, hn, { start, 0 });

	while (hn)
	{
		NODE *nd;
		EDGE tmp;

		tmp = pop(heap, hn);

		if (visit[tmp.node]) continue;

		visit[tmp.node] = 1;

		for (nd = HEAD[tmp.node].next; nd; nd = nd->next)
		{
			if (distance[nd->value] > distance[tmp.node] + nd->weight)
			{
				from[nd->value] = tmp.node;
				distance[nd->value] = distance[tmp.node] + nd->weight;
				push(heap, hn, { nd->value, distance[nd->value] });
			}
		}
	}

	printf("%d\n", distance[end]);
	
	DFS(1, end);

	putchar('\n');

	return 0;
}