[백준] 1916: 최소비용 구하기 JAVA, C++

접근

옛날에 C++로 풀었던 코드가 있어서 함께 첨부했다. 이번에 자바로 푼 방법이랑은 조금 달라서, 분명히 과거의 내가 작성한 코드일텐데 접근 방식이 다른게 새삼 신기했다. 자바 코드의 경우 입력으로 들어오는 Edge 데이터를 저장하기 위해 이너 클래스를 만들고, 2차원 ArrayList에 저장했다. 그리고 거리가 갱신된 경우 큐에 해당 간선을 넣는 방식으로 풀었다. 그런데 다익스트라 함수에서, 큐는 순서대로 넣고 빼다 보니 앞서 이미 갱신된 데이터들에 대해서 처리가 필요했다. 주석의 이미 업데이트된 경우 부분을 넣지 않으니 시간 초과가 발생했었다. c++의 경우에는 NxN 배열에 간선의 정보를 저장한 후 우선순위 큐를 사용했다. 

 

코드

JAVA 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BJ1916 {
    static class Edge{
        int from, to, cost;

        public Edge(int from, int to, int cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }
    }

    static ArrayList<ArrayList<Edge>> graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        // 입력값 저장
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        graph = new ArrayList<>();
        for (int i = 0; i <= n; i++)
            graph.add(new ArrayList<>());

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph.get(from).add(new Edge(from, to, cost));
        }

        st = new StringTokenizer(br.readLine());
        int cityA = Integer.parseInt(st.nextToken());
        int cityB = Integer.parseInt(st.nextToken());

        int[] dist = dijkstra(cityA, cityB, n);

        System.out.println(dist[cityB]);
    }

    private static int[] dijkstra(int cityA, int cityB, int n) {
        int[] dist = new int[n+1];
        Arrays.fill(dist, -1);

        // 시작지점 처리
        Queue<Edge> q = new LinkedList<>();
        q.add(new Edge(cityA, cityA, 0));
        dist[cityA] = 0;

        while(!q.isEmpty()){
            Edge cur = q.poll();

            // 이미 업데이트된 경우
            if(dist[cur.to] < dist[cur.from] + cur.cost)
                continue;

            for(Edge neighbor : graph.get(cur.to)){
                if(dist[neighbor.to] == -1 || dist[neighbor.to] > dist[neighbor.from] + neighbor.cost) {
                    dist[neighbor.to] = dist[neighbor.from] + neighbor.cost;
                    q.add(neighbor);
                }
            }
        }

        return dist;
    }
}

 

C++ 코드

#include <iostream>
#include <vector>
#include <queue>
#define INF 1000000000
using namespace std;
typedef pair<int, int> pii;

vector<vector<int>> city;
vector<int> dist;
priority_queue<pii> pq; //방문 가능한 <거리, 노드번호>를 저장한다


void pq_push(int idx){
    int s = city.size();
    for(int i = 1;i < s;i++){
        //방문 가능한 노드를 거리와 함께 pq에 삽입
        if(city[idx][i] != INF){
            if(dist[idx]+city[idx][i] < dist[i]){
                pq.push(pii(-city[idx][i], i));
                dist[i] = dist[idx]+city[idx][i];
            }
        }
    }
}

int main(){
    int n, m, a, b, c;
    int start_node, end_node;
    scanf("%d%d", &n, &m);
    city = vector<vector<int>> (n+1, vector<int> (n+1, INF));
    dist = vector<int> (n+1, INF);

    for(int i = 0;i < m;i++){
        scanf("%d%d%d", &a, &b, &c);
        city[a][b] = min(city[a][b], c);
    }

    //시작 위치는 방문 처리
    scanf("%d%d", &start_node, &end_node);
    dist[start_node] = 0;
    pq_push(start_node);

    while(!pq.empty()){
        pii cur = pq.top(); pq.pop();
        pq_push(cur.second);
    }

    printf("%d", dist[end_node]);
}