코딩 테스트 [그래프] - 최소 비용 구하기

N개의 도시가 있다. 그리고 한 도시에서 출발해 다른 도시로 도착하는 M개의 버스가 있다. A번째 도시에서 B번째 도시까지 가는 데 드는 버스 비용을 최소화하려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소 비용을 출력하라. 도시 번호는 1부터 N까지다.

(시간 제한 0.5초)

---

입력

1번째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000), 2번째줄에 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 3번째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 가장 처음에는 그 버스의 출발 도시의 번호가주어진다. 그다음에는 도착지의 도시 번호가 주어지고, 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수다. 그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시 번호화 도착점의 도시 번호가 주어진다. 출발점에서 도착점을 갈 수 있을 때만 입력으로 주어진다.

출력

1번째 줄에 출발 도시에서 도착 도시까지 가는 데 드는 최소 비용을 출력한다.

예제 입력
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

예제 출력
4

---

1단계 - 문제 분석하기

시작점과 도착점이 주어지고, 이 목적지까지 가는 최소 비용(최단 거리)를 구하는 문제이다. 또한 버스 비용의 범위가 음수가 아니기 때문에 이 문제는 다익스트라 알고리즘을 이용해 해결할 수 있다.

2단계 - 손으로 풀어 보기

1 데이터를 기반으로 그래프를 그린다. 도시는 노드로, 도시 간 버스 비용은 에지로 나타낸다.

2 그래프로 인접 리스트 배열을 만든다. 이때 배열의 자료형이 될 클래스를 만들어 도착 도시와 비용을 저장한다.

3 다익스트라 알고리즘을 수행해 최단 거리 배열에 값을 저장하고, 도착 도시의 값을 출력한다.

3단계 - sudo코드 작성하기

N(도시 수) M(버스 수)
A(인접 리스트 배열) distance(최단 거리 배열) visited(방문 배열)
startNode(시작점) endNode(도착점)

for(N만큼 반복)
{
	인접 리스트 배열 초기화
}
최단 거리 배열 초기화
방문 배열 초기화

for(M만큼 반복)
{	
	인접 리스트 배열에 데이터 저장
}

우선순위 큐 선언
우선순위 큐에 시작점 add
while(큐가 빌 때까지)
{
	현재 노드 = 큐에서 poll
    현재 노드에 방문한 적 있는지 체크
    
    for(현재 노드와 연결되있는 노드의 개수만큼 반복)
    {
    	if(다음 노드의 결과값 > 현재 노드 결과값 + 노드 사이의 값 이라면)
        {
        	다음 노드 결과값 = 현재 노드 결과값 + 노드 사이의 값
            큐에 다음 노드 add
        }
       
    }
}

도착점의 결과값 출력

4단계 - 코드 구현하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Q57 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        ArrayList<Edge57>[] A = new ArrayList[N+1];
        int[] distance = new int[N+1];
        boolean[] visited = new boolean[N+1];

        for(int i = 1; i < N+1; i++){
            A[i] = new ArrayList<Edge57>();
        }
        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());

            A[S].add(new Edge57(E, V));
        }
        st = new StringTokenizer(br.readLine());
        int startNode = Integer.parseInt(st.nextToken());
        int endNode = Integer.parseInt(st.nextToken());

        for(int i = 1; i < N+1; i++){
            distance[i] = Integer.MAX_VALUE;
        }
        distance[startNode] = 0;

        PriorityQueue<Edge57> queue = new PriorityQueue<Edge57>();
        queue.add(new Edge57(startNode, 0));

        while (!queue.isEmpty()){
            Edge57 now = queue.poll();
            int now_Node = now.targetNode;

            if(visited[now_Node])
                continue;
            visited[now_Node] = true;

            for(int i = 0; i < A[now_Node].size(); i++){
                Edge57 tmp = A[now_Node].get(i);
                int next_Node = tmp.targetNode;
                int value = tmp.value;

                if(distance[next_Node] > distance[now_Node] + value){
                    distance[next_Node] = distance[now_Node] + value;
                    queue.add(new Edge57(next_Node, distance[next_Node]));
                }
            }
        }

        System.out.println(distance[endNode]);
    }
}

class Edge57 implements Comparable<Edge57>{
    int targetNode;
    int value;
    Edge57(int targetNode, int value){
        this.targetNode = targetNode;
        this.value = value;
    }

    @Override
    public int compareTo(Edge57 o) {
        return this.value - o.value;
    }
}

---

• Do it! 알고리즘 코딩테스트 자바 편