[Algorithm] 백준_최소비용 구하기 2_11779번 (JAVA)

2025. 3. 26. 15:05·Algorithm
목차
  1. 📝문제
  2. 💡풀이
  3. 🤔Review

📝문제

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

최비용 구하기 2 : 11779번

티어 : 골드3

💡풀이

문제 유형

다익스트라

 

걸린 시간

110분

 

시간 복잡도

 

 

풀이 방법 도출

  1. 이제 가중치가 다른 경로 사이의 최소 비용 구하기 하면 바로 다익스트라가 떠오른다.
  2. 이틀 전에 풀었던 최소비용 구하기 문제와 거의 흡사하나 출력 조건에 몇가지 추가 되었다 (https://girokeulhaja.tistory.com/135)
  3. 우선순위 큐를 사용하여 인접한 배열 리스트를 검사해 최소비용을 갱신해준다.
  4. 지나간 경로 출력 하는 방법을 모르겠어서 지피티한테 물어봤다,,
  5. 그리고 StringBuilder 의 reverse() 메서드를 사용하려고 했으나 1 10 100으로 들어온 경우
  6. 001 01 1이 출력 되므로 ArrayList로 받기로 한다.
import java.util.*;
import java.io.*;
class Main{
    static ArrayList<Node>[] graph;
    static int[] dist;
    static int[] path;
    static int INF = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); //도시의 개수
        int m = Integer.parseInt(br.readLine()); //버스의 개수

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

        graph = new ArrayList[n+1];
        for(int i = 0; i <= n; i++){
            graph[i] = new ArrayList<>();
        }

        StringTokenizer st;

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

            graph[start].add(new Node(end, cost));
        }

        st = new StringTokenizer(br.readLine());
        int u = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());

        dist[u] = 0;
        dijkstra(u);

        System.out.println(dist[v]);

        StringBuilder sb = new StringBuilder();
        int now = v;
        ArrayList<Integer> list = new ArrayList<>();
        while(true){
            list.add(now);
            if(now == u) break;
            now = path[now];
        }

        Collections.reverse(list);
        for(int l : list){
            sb.append(l).append(" ");
        }
        System.out.println(list.size());
        System.out.println(sb);
    }
    public static void dijkstra(int start){
        PriorityQueue<Node> pq = new PriorityQueue<>((a,b)->a.cost);
        pq.add(new Node(start, 0));

        while(!pq.isEmpty()){
            Node node = pq.poll();
            int now = node.end;
            int cost = node.cost;

            if(cost > dist[now]) continue;

            for(Node next : graph[now]){
                int newCost = dist[now] + next.cost;
                if(newCost < dist[next.end]){
                    dist[next.end] = newCost;
                    path[next.end] = now;
                    pq.add(new Node(next.end, newCost));
                }
            }
        }
    }
}
class Node{
    int end;
    int cost;
    public Node(int end, int cost){
        this.end = end;
        this.cost = cost;
    }
}

 

🤔Review

다익스트라는 껌이지 이제 

'Algorithm' 카테고리의 다른 글

[Algorithm] 백준_Z_1074번 (JAVA) 분할정복  (0) 2025.03.28
[Algorithm] 백준_구간 합 구하기 5_11660번 (JAVA)  (0) 2025.03.27
[Algorithm] 백준_거짓말_1043번 (JAVA) 유니온 파인드  (0) 2025.03.25
[Algorithm] 백준_최소비용 구하기_1916번 (JAVA) 다익스트라  (0) 2025.03.24
[Algorithm] 백준_DNA 비밀번호_12891번 (JAVA) 슬라이딩 윈도우  (0) 2025.03.23
  1. 📝문제
  2. 💡풀이
  3. 🤔Review
'Algorithm' 카테고리의 다른 글
  • [Algorithm] 백준_Z_1074번 (JAVA) 분할정복
  • [Algorithm] 백준_구간 합 구하기 5_11660번 (JAVA)
  • [Algorithm] 백준_거짓말_1043번 (JAVA) 유니온 파인드
  • [Algorithm] 백준_최소비용 구하기_1916번 (JAVA) 다익스트라
dev_ajrqkq
dev_ajrqkq
알고리즘 천재가 될 거야
  • dev_ajrqkq
    기록이 자산이다
    dev_ajrqkq
  • 전체
    오늘
    어제
    • 분류 전체보기 (163)
      • Front-end (0)
      • Back-end (16)
        • Spring (4)
        • Java (8)
      • CS (9)
        • 데이터베이스 (5)
        • 네트워크 (4)
      • Algorithm (91)
      • 이것저것 (0)
      • 버그잡기 (1)
      • TIL (37)
      • 후기 (1)
      • 취준 (0)
  • 블로그 메뉴

    • 링크

    • 공지사항

    • 인기 글

    • 태그

      항해99
      직장인자기계발
      개발자취업
      TypeScript
      오공완
      패스트캠퍼스
      습관형성
      오블완
      99클럽
      패스트캠퍼스후기
      코딩테스트준비
      환급챌린지
      티스토리챌린지
      Til
    • 최근 댓글

    • 최근 글

    • hELLO· Designed By정상우.v4.10.2
    dev_ajrqkq
    [Algorithm] 백준_최소비용 구하기 2_11779번 (JAVA)
    상단으로

    티스토리툴바

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.