[백준/자바] 1753 - 최단경로

 

 

이 문제는 대표적인 다익스트라 문제로 유명한 최단경로 문제이다.

 

우선순위 큐에 대한 개념을 많이 까먹고 있었는데 이 문제를 통해 다시 복습할 수 있었고 다익스트라에 대한 공포를 어느정도 걷을 수 있게 된 문제였다.

 

 

 

풀이 전략

 

문제가 길고 복잡해질수록 변수와 초기값을 명확히 정의하는 것이 중요하다고 판단했다.

 

어떤 데이터 구조를 사용할지, 어디에 어떤 값을 저장해야 하는지, 시간 복잡도를 고려한 최적의 알고리즘을 적용할지, 시간 복잡도를 고려해서 어떤 알고리즘을 다익스트라 구현에 생각할지 생각했다.

 

인접 행렬과 인접 리스트로 그래프를 표현할 수 있는데 정점이 많은 경우 보통 인접 리스트를 사용해서 메모리 절약과 탐색 속도를 높이는 것이 효과적이므로 인접 리스트를 사용하기로 했다.

 

그리고 모든 가중치가 양수인 상황을 고려하고 가장 짧은 거리의 정점부터 탐색하는 우선순위 큐를 활용하여 다익스트라를 구현하기로 했다.

 

 

 

 

코드 풀이

 

어떻게 문제 풀이를 할지 생각했으므로 다음 단계로 먼저 입력값과 변수를 선정해준다.

 

 

입력값 및 변수

 

static int V,E,K; 
static List<Node>[] graph; // 그래프 저장을 위한 인접 리스트
static int[] dist; // 최단 거리 배열
static final int INF = 1000000000;

 

정점 개수 V, 간선 개수 E, 시작 정점 K

인접 리스트 graph

최단 거리 저장 배열 dist

초기값 INF

 

 

Node 클래스 정의

 

static class Node {
    int vertex, weight;

    public Node(int vertex, int weight) {
        this.vertex = vertex;
        this.weight = weight;
    }
}

 

연결된 정점 번호 변수 vertex

 

해당 간선 가중치 weight

 

다익스트라 알고리즘에서 우선순위 큐를 사용하므로 Node 객체를 저장하자.

 

 

 

 

 

입력 처리와 그래프 초기화

 

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());

st = new StringTokenizer(br.readLine());
K = Integer.parseInt(st.nextToken());
graph = new ArrayList[V+1]; // 정점 개수만큼 리스트 배열 생성
for(int i = 1; i <= V; i++) {
    graph[i] = new ArrayList<>();
}

 

graph[i] = new ArrayList<>();를 통해서 각 정점마다 연결된 리스트를 초기화한다.

 

BufferedReader와 StringTokenizer를 사용하여 빠른 입력을 처리한다.

 

 

 

 

 

 

그래프(인접 리스트) 입력 받기

 

for(int i=0; i<E; i++) {
    st = new StringTokenizer(br.readLine());
    int u = Integer.parseInt(st.nextToken());
    int v = Integer.parseInt(st.nextToken());
    int w = Integer.parseInt(st.nextToken());

    // 방향 그래프이므로 u -> v 간선만 저장
    graph[u].add(new Node(v, w));
}

 

u -> v 방향의 간선과 가중치 w를 인접 리스트(graph[u])에 저장한다.

 

방향 그래프이므로 graph[v]에는 추가하지 않는다.

 

 

 

최단 거리 배열 초기화

 

dist = new int[V+1];
Arrays.fill(dist, INF);
dist[K] = 0; // 시작 정점의 최단 거리는 0으로 설정

 

dist를 INF로 초기화해서 처음엔 모든 정점이 도달 불가능한 상태로 설정한다.

 

dist[K] = 0; 을 통해 최단 거리는 0으로 설정한다.

 

 

 

우선순위 큐 선언

 

PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
    @Override
    public int compare(Node n1, Node n2) {
        return n1.weight - n2.weight;
    }
});
pq.add(new Node(K, 0)); // 시작 정점을 큐에 추가

 

우선순위 큐를 사용하여 가중치가 작은 순서대로 탐색할 수 있도록 정렬한다.

 

compare() 메서드를 이용하여 가중치가 작은 순으로 정렬한다.

 

시작정점 K를 우선순위 큐에 거리 0으로 넣고 탐색을 시작한다.

 

 

 

다익스트라 알고리즘

while(!pq.isEmpty()) {
    Node current = pq.poll();
    int currentVertex = current.vertex;
    int currentWeight = current.weight;

    // 기존 최단 거리보다 크다면 무시
    if (currentWeight > dist[currentVertex]) continue;

    for(Node neighbor : graph[currentVertex]) {
        int nextVertex = neighbor.vertex; // 인접 정점
        int edgeWeight = neighbor.weight; // 간선 가중치
        int newWeight = currentWeight + edgeWeight; // 새로운 가중치 계산

        if(newWeight < dist[nextVertex]) {
            dist[nextVertex] = newWeight; // 최단 거리 갱신
            pq.add(new Node(nextVertex, newWeight)); // 큐에 추가하여 다음 탐색 진행
        }
    }
}

 

 

우선순위 큐에서 현재까지 최단 거리가 가장 짧은 정점을 꺼낸다.

 

이미 갱신된 최단 거리보다 크다면 무시 (불필요한 탐색 방지).

 

현재 정점과 연결된 모든 인접 정점 탐색
→ 기존 dist[nextVertex]보다 newWeight가 작다면 최단 거리 갱신한다.
→ 최단 거리 갱신된 정점을 다시 우선순위 큐에 추가한다.

 

 

 

결과 출력

 

for(int i=1; i<=V; i++) {
    if(dist[i] == INF) {
        System.out.println("INF"); // 도달 불가능한 정점
    } else {
        System.out.println(dist[i]); // 최단 거리 출력
    }
}

 

 

dist[i] == INF -> 도달할 수 없는 경우 INF를 출력한다.

 

그렇지 않다면 해당 정점까지의 최단 거리를 출력한다.

 

 

 

최종 코드

 

package baekjoon;


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

public class Boj_1753 {
    static int V,E,K;
    static List<Node>[] graph; //그래프 저장 인접 리스트
    static int[] dist;
    static final int INF = 1000000000;

    static class Node {
        int vertex, weight;

        public Node(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        graph = new ArrayList[V+1];
        for(int i = 1; i <= V; i++) {
            graph[i] = new ArrayList<>();
        }

        for(int i=0; i<E; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            //방향이니까 u -> v 간선만
            graph[u].add(new Node(v, w));
        }

        dist = new int[V+1];
        Arrays.fill(dist, INF);

        //시작 정점은 0
        dist[K] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node n1, Node n2) {
                return n1.weight - n2.weight;
            }
        });

        pq.add(new Node(K, 0));

        while(!pq.isEmpty()) {

            //정점 꺼내자
            Node current = pq.poll();
            int currentVertex = current.vertex;
            int currentWeight = current.weight;

            // 현재 정점까지의 거리가 기존 최단 거리보다 크다면 무시
            if (currentWeight > dist[currentVertex]) continue;

            for(Node neighbor : graph[currentVertex]) {
                int nextVertex = neighbor.vertex; //인접 정점
                int edgeWeight = neighbor.weight; //간선 가중치
                int newWeight = currentWeight + edgeWeight; //새로운 가중치

                if(newWeight < dist[nextVertex]) {
                    dist[nextVertex] = newWeight;
                    pq.add(new Node(nextVertex, newWeight)); //갱신정점 추가
                }
            }
        }
        for(int i=1; i<=V; i++) {
            if(dist[i] == INF) {
                System.out.println("INF");
            } else {
                System.out.println(dist[i]);
            }

        }
    }

}