[BOJ/Gold3] 11779번 최소비용 구하기 2 - JAVA[자바]

2025. 1. 8. 22:52·PS/백준

난이도 : 골드 3

유형 : 최단 경로 / 다익스트라

링크 : https://www.acmicpc.net/problem/11779 

구현 시간 : 30분

 

 

백준 문제 이미지

 

 

문제풀이

해당 문제를 해결하기 위해서 다익스트라 알고리즘을 사용하여 출발 도시에서 각 노드(도시)까지의 최소 시간을 구하고, 동시에 이전 방문 노드를 저장해야 한다.

 

이를 위해 인접한 노드를 방문하며 최소 시간을 distance[] 배열에 갱신하고, 이와 함께 이전 노드를 preN[] 배열에 저장한다.

이렇게 하면 특정 노드에 도달했을 때 해당 노드로 오기까지의 이전 노드를 추적할 수 있다.

이후 최단 거리를 출력하고, Stack을 사용하여 방문 순서를 역순으로 출력한다.

 

핵심은 다익스트라 알고리즘에서 distance[] 배열을 갱신할 때, 이전 노드를 preN[] 배열에 함께 기록하여 경로 추적이 가능하다는 것을 이해하는게 중요하다.

 

 

 

1차 시도 - 통과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {

    static StringTokenizer st;
    static int N;
    static int M;
    
    static int start;
    static int end;
    
    static int[] distance, preN;
    static List<Node>[] list;
    
    static class Node implements Comparable<Node> {
        int idx;
        int cost;
        
        public Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Node o) {
            return Integer.compare(cost, o.cost);
        }
    }
    
    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());
        
        distance = new int[N + 1];      // 노드 별 최소 거리 저장
        preN = new int[N + 1];          // 이전 방문 노드 저장
        list = new List[N + 1];         // 노드 연결, 비용 정보 저장
        Arrays.fill(distance, Integer.MAX_VALUE);
        
        for (int i = 1; i < N + 1; i++) {
            list[i] = 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());
            list[from].add(new Node(to, cost));
        }
        
        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
        
        dijkstra();
        System.out.println(distance[end]);
        
        // 역추적 시작
        Stack<Integer> stack = new Stack<>();
        stack.push(end);
        int cnt = 1;
        
        while (preN[end] != 0) {
            cnt++;
            stack.push(preN[end]);
            end = preN[end];
        }
        
        System.out.println(cnt);
        
        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }
    
    public static void dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        distance[start] = 0;
        
        while(!pq.isEmpty()) {
            Node node = pq.poll();
            int idx = node.idx;
            int cost = node.cost;
            
            if (cost > distance[idx]) {
                continue;
            }
            
            for (Node next : list[idx]) {
                int nextIdx = next.idx;
                int newCost = cost + next.cost;
                
                if (distance[nextIdx] > newCost) {
                    distance[nextIdx] = newCost;
                    pq.offer(new Node(nextIdx, newCost));
                    // 이전 방문 노드 추가
                    preN[nextIdx] = idx;
                }
            }
        }
    }
}

'PS > 백준' 카테고리의 다른 글

[BOJ/Gold5] 15686번 치킨 배달 - JAVA[자바]  (1) 2025.01.15
[BOJ/Gold3] 1005번 ACM Craft - JAVA[자바]  (0) 2025.01.09
[BOJ/Silver1] 2156번 포도주 시식 - JAVA[자바]  (0) 2025.01.05
[BOJ/Silver1] 9465번 스티커 - JAVA[자바]  (2) 2025.01.04
[BOJ/Silver3] 2193번 이친수 - JAVA[자바]  (1) 2025.01.04
'PS/백준' 카테고리의 다른 글
  • [BOJ/Gold5] 15686번 치킨 배달 - JAVA[자바]
  • [BOJ/Gold3] 1005번 ACM Craft - JAVA[자바]
  • [BOJ/Silver1] 2156번 포도주 시식 - JAVA[자바]
  • [BOJ/Silver1] 9465번 스티커 - JAVA[자바]
hongjeZZ
hongjeZZ
백엔드 개발자로서의 성장 과정을 기록합니다.
  • hongjeZZ
    Hong's Dev Note
    hongjeZZ
  • 전체
    오늘
    어제
    • 분류 전체보기 (40)
      • Back-End (9)
        • Java (0)
        • Spring (9)
        • Docker & Kubernetes (0)
      • Database (0)
        • MySQL (0)
        • Redis (0)
        • 데이터베이스 (0)
      • CS (4)
        • 운영체제 & 네트워크 (1)
        • 아키텍쳐 & 분산시스템 (0)
      • 회고 (0)
      • PS (27)
        • 백준 (16)
        • 알고리즘 (2)
        • 프로그래머스 (9)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

    • GitHub
  • 공지사항

  • 인기 글

  • 태그

    운영체제
    그리디
    그래프 이론
    스택
    우선순위큐
    컴퓨터구조
    dfs
    시뮬레이션
    BFS
    문자열
    구현
    spirng boot
    DP
    Redis
    Stomp
    CS
    웹소켓
    큐
    Spring
    mongodb
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
hongjeZZ
[BOJ/Gold3] 11779번 최소비용 구하기 2 - JAVA[자바]
상단으로

티스토리툴바