[BOJ][백준 1916] 최소비용 구하기 - C++

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

1916번: 최소비용 구하기

백준 사이트의 1916번 문제, 최소비용 구하기 문제다.

본인은 C++로 문제풀이를 진행하였다.

---

0. 문제 읽기

문제의 입력과 출력

• 가중치가 있는 그래프에서 최소비용을 구하는 문제 => Dijkstra 알고리즘!

---

1. 문제풀이 아이디어

• 가중치가 있는 그래프에서 최소비용을 구하는 알고리즘인 Dijkstra의 기본 형식이다.
  • 참고1) 가중치가 없는 그래프의 최단경로 => BFS 알고리즘 (너비 우선 탐색 알고리즘)
  • 참고2) Dijkstra알고리즘은 가중치에 음수가 포함된 경우에는 사용할 수 없다!
• 단방향 그래프이다.
• Dijkstra 알고리즘 구현에는 for문을 사용하는 방법(시간복잡도: O(N^2))과 우선순위 큐를 사용하는 방법(시간복잡도: O(NlogN)) 두가지가 있다.
• 나는 그중에서 우선순위 큐를 사용한 방법으로 문제를 해결하였다.

---

2. 코드 핵심 부분

1) 입력을 받고 인접 리스트를 준비하는 input 함수,

   구조체 벡터를 사용하여 출발지, 도착지, 비용을 저장한다.

   단방향 그래프기 때문에 반대방향을 기록하지 않았다.

   인접 리스트가 아닌 인접 행렬을 사용하는 방법은 메모리 측면에서 상당히 비효율적이기에

   인접 리스트를 애용하자! (특정 경우에서는 인접 행렬이 유리한 경우도 존재)

void input() {
	cin >> N >> M;
	int from, to, cost;
	for (int j = 0; j < M; j++) {
		cin >> from >> to >> cost;
		Bus[from].push_back({ to, cost });
	}
	cin >> st >> ed;
}

 

2) dijkstra 알고리즘 구현 함수,

   기본적인 틀 그대로 사용하여 특별한 점은 없다.

void dijkstra(int start) {
 
    priority_queue<Edge> pq;
    pq.push({ start, 0 });

    // 각 정점까지의 최단 비용을 저장하기 위한 dist 배열을 초기화
    int dist[1001] = { 0 };
    int Max = 21e8;
    for (int i = 1; i <= N; i++) {
        dist[i] = Max;
    }
    dist[start] = 0;

    // 방문한 정점인지 확인하기 위한 visited 배열을 초기화
    int visited[1001] = { 0 };

    while (!pq.empty()) {
        // 우선순위 큐에서 가장 비용이 적은 정점을 선택
        Edge now = pq.top();
        pq.pop();

        // 이미 방문한 정점인 경우 스킵
        if (visited[now.to])
            continue;
        visited[now.to] = 1;

        // 현재 정점과 연결된 정점들을 탐색
        for (int i = 0; i < Bus[now.to].size(); i++) {
            Edge next = Bus[now.to][i];
            int ncost = dist[now.to] + next.cost;

            // 다음 정점까지의 비용이 현재까지 계산한 최단 비용보다 크거나 같으면 스킵
            if (dist[next.to] <= ncost)
                continue;

            // 다음 정점까지의 최단 비용을 갱신하고 우선순위 큐에 추가
            dist[next.to] = ncost;
            pq.push({ next.to, ncost });
        }
    }

    // 도착 정점까지의 최단 비용을 저장
    Ans = dist[ed];
}

---

3. 전체 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct Edge {
	int to;
	int cost;
    
	// 우선순위 큐를 사용하여 최소 비용의 정점을 선택하기 위해 Edge 구조체에 operator<를 정의
	bool operator < (Edge next) const {
		if (cost < next.cost)
			return false;
		if (cost > next.cost)
			return true;
		return false;
	}
};

// 필요한 전역 변수들 
int N, M;
vector<Edge> Bus[1001];
int st, ed;
int Ans;

void input() {
	cin >> N >> M;
	int from, to, cost;
	for (int j = 0; j < M; j++) {
		cin >> from >> to >> cost;
		Bus[from].push_back({ to, cost });
	}
	cin >> st >> ed;
}

void dijkstra(int start) {
 
    priority_queue<Edge> pq;
    pq.push({ start, 0 });

    // 각 정점까지의 최단 비용을 저장하기 위한 dist 배열을 초기화
    int dist[1001] = { 0 };
    int Max = 21e8;
    for (int i = 1; i <= N; i++) {
        dist[i] = Max;
    }
    dist[start] = 0;

    // 방문한 정점인지 확인하기 위한 visited 배열을 초기화
    int visited[1001] = { 0 };

    while (!pq.empty()) {
        // 우선순위 큐에서 가장 비용이 적은 정점을 선택
        Edge now = pq.top();
        pq.pop();

        // 이미 방문한 정점인 경우 스킵
        if (visited[now.to])
            continue;
        visited[now.to] = 1;

        // 현재 정점과 연결된 정점들을 탐색
        for (int i = 0; i < Bus[now.to].size(); i++) {
            Edge next = Bus[now.to][i];
            int ncost = dist[now.to] + next.cost;

            // 다음 정점까지의 비용이 현재까지 계산한 최단 비용보다 크거나 같으면 스킵
            if (dist[next.to] <= ncost)
                continue;

            // 다음 정점까지의 최단 비용을 갱신하고 우선순위 큐에 추가
            dist[next.to] = ncost;
            pq.push({ next.to, ncost });
        }
    }

    // 도착 정점까지의 최단 비용을 저장
    Ans = dist[ed];
}

void output() {
    // 최소 비용을 출력
    cout << Ans;
}

// 메인함수
int main() {

	// input
	input();

	// solve
	dijkstra(st);

	// output
	output();

	return 0;
}

---

4. 문제 풀이를 마치며..

백준 채점 결과

명쾌하게 사용할 알고리즘이 딱 정해져있는 문제라 설계는 정말 쉬웠다.

 

그런데 Dijkstra 알고리즘 문제를 최근에 풀지 않았더니

틀 자체가 기억이 가물가물했다...

 

열심히 배워놨던 알고리즘이 스르륵 기억에서 흘러나가는 경험이 자주 있다.

코딩 테스트에 자주 출제되는 DFS, BFS알고리즘 외에도

다양하게 문제를 풀어 복습을 철저히 해야겠다.