문제

문제 바로가기

풀이 코드

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

public class Main {
    static int n; // 도시의 개수 5개
    static int m; // 버스의 개수 8개
    static boolean[] visited;
    static ArrayList<ArrayList<Node>> list;
    static int[] dist; // 거리를 계속해서 더함
    static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        list = new ArrayList<>();
        dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE); // 거리는 전부 다 최댓값으로
        visited = new boolean[n + 1];

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

        for (int i = 0; i < m; i++) { // ArrayList안에 노드 정보들을 ArrayList로 넣고
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            list.get(start).add(new Node(end, w));
        }

        st = new StringTokenizer(br.readLine());
        int s_node = Integer.parseInt(st.nextToken()); // 주어진 시작 노드
        int e_node = Integer.parseInt(st.nextToken()); // 주어진 도착 노드

//        for (int i = 1; i < list.length; i++) {
//            System.out.println(list[i].toString());
//        }

        dijkstra(s_node);
        System.out.println(dist[e_node]);

    }

    static void dijkstra(int start) {
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.offer(new Node(start, 0)); // 출발 도시와 거리 큐에 담고
        dist[start] = 0;

        // 시간 초과 코드
//		while (!queue.isEmpty()) {
//			Node queNode = queue.poll();
//			visited[queNode.end] = true;
//			for (Node n : list.get(queNode.end)) { // 출발 지점으로부터 도착할 수 있는 노드와 가중치 정보를 가져오고
//				if (!visited[n.end] && dist[n.end] > dist[queNode.end] + n.w) { // 바로 갈 수 있는 거리와 거쳐서 가는 거리 중 짧은 것으로 대체
//					dist[n.end] = dist[queNode.end] + n.w;
//					queue.offer(new Node(n.end, dist[n.end]));
//				}
//			}
//		}

        while (!queue.isEmpty()) {
            System.out.println(queue);
            Node queNode = queue.poll();
            if (!visited[queNode.end]) {
                visited[queNode.end] = true;
                for (Node n : list.get(queNode.end)) { // 출발 지점으로부터 도착할 수 있는 노드와 가중치 정보를 가져오고
                    if (!visited[n.end] && dist[n.end] > dist[queNode.end] + n.w) { // 바로 갈 수 있는 거리와 거쳐서 가는 거리 중 짧은 것으로 대체
                        dist[n.end] = dist[queNode.end] + n.w;
                        queue.offer(new Node(n.end, dist[n.end]));
                    }
                }
            }
        }
    }

}

class Node implements Comparable<Node> {
    int end, w;

    public Node(int city, int w) {
        this.end = city;
        this.w = w;
    }

    @Override
    public int compareTo(Node o) {
        return w - o.w;
    }

    @Override
    public String toString() {
        // TODO Auto-generated method stub
        return "end: " + end + " w: " + w;
    }
}

처음 풀어보는 다익스트라 알고리즘 문제.. 우선 다익스트라 알고리즘에 대해서 먼저 알아본 후에 문제를 접근해야 구현 단계로 넘어갈 수 있었기에 유튜브에서 따로 조금 영상을 찾아봤습니다!
다익스트라 알고리즘은 위 문제와 같이 시작 노드에서 다른 모든 노드까지 도달하기까지에 있어 최단 경로를 구하는 알고리즘입니다. 현재 문제에서는 주어진 출발도시에서 도착도시까지 가는데 드는 최소 비용을 출력하라고 나와있습니다.

이때, 이 문제에서 처음으로 해본 것들이 많은데 그 중 ArrayList안에 또 다시 ArrayList를 넣는겁니다! 안에 생성한 ArrayList는 Node 클래스타입인데 이때 오류를 많이 겪었던 것이 선언을 하고 끝이 아니라 for문을 통해 ArrayList안의 list도 초기화를 해주는겁니다!

그러고 난 후, 주어진 입력값으로 시작노드에서 도착노드까지 드는 비용을 넣어주고, 다익스트라 메소드 안에서는 while문을 통해 값을 꺼낸 후, 제일 최소 비용에 해당하는 노드 먼저 가져옵니다. (이때 헷갈렸던 부분이 저는 큐 안에 이미 우선순위 큐라 정렬이 되어있는 줄 알았는데 그게 아니라 poll을 할 때 제일 작은 값 먼저 가져오더군요..)

그렇게 큐 안의 노드를 가져온 후, 바로 list의 인덱스로 접근해서 foreach문으로 꺼내게 되면 시간 초과가 발생하기에 방문하지 않은 노드에 한해서 방문체크를 해주고 거리를 비교해서 최단 거리로 dist안의 값을 바꿔주면 됩니다!

그렇게 실행하고 난 후에는 마지막으로 도착해야하는 노드까지의 거리를 dist에서 구해주면 됩니다!