[백준] 최소 비용 구하기 (다익스트라)

별것 아닌거 가지고 상당히 오랜시간 삽질했다. 이번 문제는 다익스트라 알고리즘 기본 문제이며, 입력 값에 신경을 써야 하는 문제다.

 

백준 1916번 다익스트라 기본 문제

이 문제의 입력값은 아래와 같다.

 

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

 

코드를 보며 이번 문제에 대해 분석해보자.

 

#include <stdio.h>
#define MAX 1001
#define INFI 999999999

// 출발지서 각 도시간 최소 비용
int D[MAX];

// 방문기록
int Visited[MAX];
int Map[MAX][MAX];

void Dijkstra (int maxV, int startV, int destV) {
	// 최소 거리를 INFI로 초기화
	for (int i = 1; i <= maxV; i++) {
		D[i] = INFI;
	}
	
	// 출발지 거리 초기화
	D[startV] = 0;
	
	// 출발지에서 모든 정점을 체크
	for (int i = 1; i <= maxV; i++) {
		// 최소값 초기화
		int min = INFI;
		
		// 가중치가 가장 작은 값 구학
		for (int j = 1; j <= maxV; j++) {
			if (!Visited[j] && min > D[j]) {
				min = D[j];
				startV = j;
			}
		}
		
		// 방문 표시
		Visited[startV] = 1;
		
		// 인접 정점 체크
		for (int nextV = 1; nextV <= maxV; nextV++) {
			// 이동 가능하고, 출발지에서 K 까지의 총비용 > 출발지에서 v를 거쳐 k까지 가는 총
			if (Map[startV][nextV] != INFI && D[nextV] > D[startV] + Map[startV][nextV]) {
				D[nextV] = D[startV] + Map[startV][nextV];
			}
		}
	}
	
	printf("%d\n", D[destV]);
}

void initMap () {
	for (int y = 0; y < MAX; y++) {
		for (int x = 0; x < MAX; x++) {
			Map[y][x] = INFI;
		}
	}
}

int main(void) {
	// 변수 선언
	int S = 0;
	int D = 0;
	int N = 0;
	int M = 0;
	
	// INFI로 맵 초기화
	initMap();
	
	// 입력 시작
	scanf("%d", &N);
	scanf("%d", &M);
	
	for (int i = 0; i < M; i++) {
		int s = 0;
		int d = 0;
		int w = 0;
		
		scanf("%d %d %d", &s, &d, &w);
		if (Map[s][d] > w) {
			Map[s][d] = w;
		}
	}
	
	scanf("%d %d", &S, &D);
	
	Dijkstra(N, S, D);
	
	return 0;
}

이번 문제에서 짚고 넘어가야할 점은 아래와 같다.

 

다익스트라 알고리즘

 

BFS, 탐욕 알고리즘, 우선 순위 큐의 개념이 같이 사용되는 복합 알고리즘으로 가중치가 있는 그래프에서 사용되는 알고리즘이다. 특정 시작 정점에서 도착 정점까지의 최소 비용을 계산할 때 사용한다. 시작 정점에서 도착 정점의 최소 비용을 구하기 위해서 다른 모든 정점의 거리를 알아야한다. 음의 가중치가 나오면 다익스트라를 사용할 수 없으며, 벨만-포드 알고리즘으로만 구할 수 있음을 알아두자.

 

다익스트라 알고리즘의 동작 방식은 "알고리즘 기본" 게시판에 작성 후 링크를 추가하도록 한다.

 

우선 순위 큐

 

이 문제는 일반 BFS 처럼 일반 큐를 사용해서 할 수 있으나, 현재 코드에서는 우선 순위 큐를 도입하였다.

// 최소값 초기화
int min = INFI;

// 가중치가 가장 작은 값 구학
for (int j = 1; j <= maxV; j++) {
  if (!Visited[j] && min > D[j]) {
    min = D[j];
    startV = j;
  }
}

인접 정점을 만나는 즉시 큐에 등록하는 방식과는 달리, 현재 인접한 정점에서 가장 비용이 적은 정점을 골라 방문하는 방식이다. C언어에서는 우선순위 큐를 구현하는 것이 힘들기 때문에 위와 같이 간단하게 구현하였다.

 

단방향 그래프

 

이 문제는 양방향 그래프 문제가 아니다. 따라서, 값을 인접 행렬에 넣을 때의 순서와 탐색 때의 인덱스의 개념이 일치해야한다. 예를 들어, 입력 값은 Map[startV][destV] 라고 했을 때, Map[dest][startV]는 서로 호환되지 않기 때문에 엉뚱한 답이 나오거나 루프가 아예 돌지 않는 점을 주의해야 한다.

 

입력 값에 주의

 

입력 값이 이렇게 올 수도 있다.

3 4
1 2 3
1 2 10
1 3 1
2 3 1
1 2

입력 값이 1 -> 2 = 3 / 1 -> 2 = 10 일 경우 아무런 처리를 하지 않으면 마지막 10이 입력 되므로, 결과 값이 3이 아닌 10이 나와버린다. 이미 가중치가 입력 되었는지와 입력된 가중치 > 새로 입력된 가중치 일 때만 인접 행렬에 저장한다. 그렇지 않으면 어디서 틀렸는지 찾을 수가 없다.