[C] 백준 - 1916번: 최소비용 구하기

9월 8일(금) - 그래프와 순회 (1916번)

1916번: 최소비용 구하기

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 1

(풀이출처 -> https://kim1124.tistory.com/19)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#define INF 987654321

#include <stdio.h>

int map[1001][1001];

int distance[1001];
int visited[1001];

void dijkstra(int N, int start, int end)
{
	for (int i = 1; i <= N; i++)
	{
		distance[i] = INF;
	}

	distance[start] = 0;
	for (int i = 1; i <= N; i++)
	{
		// 우선순위 큐 간단 구현
		int min = INF;

		for (int j = 1; j <= N; j++)
		{
			if (!visited[j] && min > distance[j])
			{
				min = distance[j];
				start = j;
			}
		}

		visited[start] = 1;
		for (int next = 1; next <= N; next++)
		{
			if (map[start][next] != INF && distance[next] > distance[start] + map[start][next])
			{
				distance[next] = distance[start] + map[start][next];
			}
		}
	}

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

int main(void)
{
	int N, M;
	scanf("%d", &N);
	scanf("%d", &M);

	for (int i = 0; i < 1001; i++)
	{
		for (int j = 0; j < 1001; j++)
		{
			map[i][j] = INF;
		}
	}

	int start, end, weight;
	for (int i = 0; i < M; i++)
	{
		scanf("%d %d %d", &start, &end, &weight);

		if (map[start][end] > weight)
		{
			map[start][end] = weight;
		}
	}

	int target_start, target_end;
	scanf("%d %d", &target_start, &target_end);

	dijkstra(N, target_start, target_end);

	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 2

(풀이출처 -> https://www.acmicpc.net/source/65473945)

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#define INF 987654321

#include <stdio.h>
#include <stdlib.h>

int MIN(int x, int y)
{
    return ((x < y) ? (x) : (y));
}

typedef struct _BUS
{
    int departure, arrival, cost;
    struct _BUS* last;
    struct _BUS* next;
} BUS;

int* sumCost;
int* Queue, front, end = 1;
BUS* busCity;
BUS* busInput;

int compare(const void* bus1, const void* bus2)
{
    BUS BUS1 = *(BUS*)bus1;
    BUS BUS2 = *(BUS*)bus2;
    if (BUS1.departure > BUS2.departure)
        return 1;
    if (BUS1.departure == BUS2.departure)
        return BUS1.arrival - BUS2.arrival;
    return -1;
}

int unique(int size)
{
    int idx = 0;
    busInput[0].next = NULL;
    for (int i = 1; i < size; i++)
    {
        if (busInput[i].departure == busInput[idx].departure && busInput[i].arrival == busInput[idx].arrival)
            busInput[idx].cost = MIN(busInput[idx].cost, busInput[i].cost);
        else
        {
            busInput[++idx] = busInput[i];
            busInput[idx].next = NULL;
        }
    }
    return ++idx;
}

void insert(int size)
{
    for (int i = 0; i < size; i++)
    {
        if (busCity[busInput[i].departure].next == NULL)
        {
            busCity[busInput[i].departure].next = &busInput[i];
            busCity[busInput[i].departure].last = &busInput[i];
        }
        else
        {
            busCity[busInput[i].departure].last->next = &busInput[i];
            busCity[busInput[i].departure].last = &busInput[i];
        }
    }
}

void doQueue(int start)
{
    Queue[0] = start;
    sumCost[start] = 0;
    while (front < end)
    {
        BUS* tmp = busCity[Queue[front]].next;
        while (tmp != NULL)
        {
            if (sumCost[tmp->departure] + tmp->cost < sumCost[tmp->arrival])
            {
                sumCost[tmp->arrival] = sumCost[tmp->departure] + tmp->cost;
                Queue[end++] = tmp->arrival;
            }
            tmp = tmp->next;
        }
        front++;
    }
}

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

    sumCost = (int*)malloc(sizeof(int) * (N + 1));
    busCity = (BUS*)malloc(sizeof(BUS) * (N + 1));
    for (int i = 1; i <= N; i++)
    {
        sumCost[i] = INF;
        busCity[i].next = NULL;
        busCity[i].last = &busCity[i];
    }

    busInput = (BUS*)malloc(sizeof(BUS) * M);

    for (int i = 0; i < M; i++)
        scanf("%d %d %d", &busInput[i].departure, &busInput[i].arrival, &busInput[i].cost);
    qsort(busInput, M, sizeof(BUS), compare);

    M = unique(M);
    insert(M);
    Queue = (int*)malloc(sizeof(int) * M);

    int D, A;
    scanf("%d %d", &D, &A);

    doQueue(D);
    printf("%d", sumCost[A]);
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ