[JAVA] 백준 1916 - 최소 비용 구하기

2024. 4. 10. 20:44·PS/다익스트라

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

 

1916번: 최소비용 구하기

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그

www.acmicpc.net


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


public class Main {

    public static int N;
    public static int V;
    public static ArrayList<Node>[] adjacentList;
    public static int[] table;
    public static HashSet<Integer> set = new HashSet<>();
    public static boolean[] visited;
    public static PriorityQueue<Node> queue = new PriorityQueue<>();

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        V = Integer.parseInt(br.readLine());
        table = new int[N + 1];
        Arrays.fill(table, Integer.MAX_VALUE);
        adjacentList = new ArrayList[N + 1];
        visited = new boolean[N + 1];
        for (int i = 0; i <= N; i++) {
            adjacentList[i] = new ArrayList<>();
        }
        for (int t = 0; t < V; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            adjacentList[u].add(new Node(v, w));
        }
        StringTokenizer st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        table[start] = 0;
        System.out.println(dijkstra(start, end));
    }

    public static int dijkstra(int start, int end) {

        queue.offer(new Node(start, 0));

        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            if(set.contains(curNode.num)){
               continue;
            }
            set.add(curNode.num);
            for (Node childNode : adjacentList[curNode.num]) {
                if (table[childNode.num] > table[curNode.num] + childNode.weight) {
                    table[childNode.num] = table[curNode.num] + childNode.weight;
                    queue.add(new Node(childNode.num, table[childNode.num]));

                }
            }


        }
        return table[end];
    }
}


class Node implements Comparable<Node> {
    int num;
    int weight;

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

    public Node() {
    }

    @Override
    public String toString() {
        return "[" + num + ", " + weight + "]";


    }

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

}

 

 

한노드를 방문했는지 확인하는 HashSet이 필요하다.

 

다익스트라 알고리즘상 O(V^2)이되게 로직을 구현해야한다.

로직을 조금 실수하면 space complexity나 time complexity를 초과하기때문에 조심해야한다.

특히 set을 언제추가하고 continue해야할지가 그 과정의 핵심이다.

 

저작자표시 비영리 변경금지 (새창열림)

'PS > 다익스트라' 카테고리의 다른 글

[JAVA] 백준 1753 - 최단경로  (0) 2024.04.09
[JAVA] 백준 1504 - 특정한 최단 경로  (0) 2024.04.08
'PS/다익스트라' 카테고리의 다른 글
  • [JAVA] 백준 1753 - 최단경로
  • [JAVA] 백준 1504 - 특정한 최단 경로
keemjoonsung
keemjoonsung
  • keemjoonsung
    구동
    keemjoonsung
  • 전체
    오늘
    어제
  • keemjoonsung
    • 분류 전체보기 (81)
      • Projects (7)
        • web (4)
        • plugin (3)
      • Trouble Shootings (5)
        • 성능 개선 (4)
        • 버그 해결 (1)
      • Backend (7)
        • Spring Boot (5)
        • Java (0)
        • Elasticsearch (1)
        • Redis (1)
      • PS (50)
        • 자료구조 (11)
        • 다이나믹프로그래밍 (18)
        • 브루트포스(dfs,bfs,backtracking) (13)
        • 구현 (2)
        • 이분탐색 (1)
        • 그리디 (0)
        • 다익스트라 (3)
        • 기타 알고리즘 (2)
      • Cloud (5)
        • AWS (2)
        • GCP (3)
      • CS (5)
        • network (1)
        • algorithm (4)
      • Etc (2)
  • 블로그 메뉴

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

  • 공지사항

  • 인기 글

  • 태그

    브루트포스
    스프링
    다이나믹프로그래밍
    스프링부트
    자바
    Plugin
    jpa
    다익스트라
    intellj
    헥사고날 아키텍쳐
    dp
    GCP
    우선순위큐
    Spring
    dfs
    레디스
    java
    코딩테스트
    스프링 부트
    페이지
    spring boot
    코테
    baekjoon
    redis
    배포
    BFS
    ps
    백준
    헥사고널
    인텔리제이
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
keemjoonsung
[JAVA] 백준 1916 - 최소 비용 구하기
상단으로

티스토리툴바