[백준/JAVA] 1916번: 최소비용 구하기

🔺 문제

1916번: 최소비용 구하기

 

🔺 코드

- 코드1)

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[] D;             // 🎈 최단 경로 배열 🎈
    static ArrayList<Node>[] A; // 인접 리스트
    static boolean[] visited;   // 방문 배열
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        
        visited = new boolean[N+1];
        
        // 최단 경로 배열 초기화
        D = new int[N+1];
        Arrays.fill(D, Integer.MAX_VALUE);
        
        // 인접 리스트 초기화
        A = new ArrayList[N+1];
        for(int i = 0 ; i <= N ; i++) {
            A[i] = new ArrayList<>();
        }
        
        // 그래프 입력 받기
        while(M --> 0) {
            st = new StringTokenizer(br.readLine()," ");
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            
            A[S].add(new Node(E, V));
        }
        
        // 출발 도시, 도착 도시 입력 받기
        st = new StringTokenizer(br.readLine()," ");
        int startCity = Integer.parseInt(st.nextToken());
        int endCity = Integer.parseInt(st.nextToken());
        
        // 다익스트라 수행
        System.out.println(dijkstra(startCity, endCity));
    }
    
 
    // 다익스트라 
    public static int dijkstra(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        
        D[start] = 0;
        
        while(!pq.isEmpty()) {
            Node nowNode = pq.poll();
            
            if(!visited[nowNode.node]) {
                visited[nowNode.node] = true;
 
                for(Node next : A[nowNode.node]) {
                    if(!visited[next.node] && D[next.node] > D[nowNode.node] + next.value) {
                        D[next.node] = D[nowNode.node] + next.value;
                        pq.add(new Node(next.node, D[next.node]));
                    }
                }
            }
        }
        return D[end];
    }
}
 
class Node implements Comparable<Node>{
    int node, value;
    
    Node(int node, int value) {
        this.node = node;
        this.value = value;
    }
    
    @Override
    public int compareTo(Node e) {
        return this.value - e.value;
    }
}

 

 

- 코드2)

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M;
    static int[] D;             // 최단 경로 배열
    static ArrayList<Node>[] A; // 인접 리스트
    static boolean visited[];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        
        visited = new boolean[N+1];
        D = new int[N+1];
        Arrays.fill(D, Integer.MAX_VALUE);
        
        A = new ArrayList[N+1];
        for(int i = 0 ; i <= N ; i++) {
            A[i] = new ArrayList<>();
        }
        
        while(M --> 0) {
            st = new StringTokenizer(br.readLine()," ");
            int S = Integer.parseInt(st.nextToken());
            int E = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            
            A[S].add(new Node(E, V));
        }
        
        st = new StringTokenizer(br.readLine()," ");
        int startCity = Integer.parseInt(st.nextToken());
        int endCity = Integer.parseInt(st.nextToken());
        
        System.out.println(dijkstra(startCity, endCity));
    }
    
    
    public static int dijkstra(int start, int end) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        
        D[start] = 0;
        //visited[start] = true;
        
        while(!pq.isEmpty()) {
            Node nowNode = pq.poll();
 
            // ** 변경된 부분 **
            if(visited[nowNode.node]) continue; // 중복 방지
            visited[nowNode.node] = true;
            
            for(Node next : A[nowNode.node]) {
                if(D[next.node] > D[nowNode.node] + next.value) {
                    D[next.node] = D[nowNode.node] + next.value;
                    pq.offer(new Node(next.node, D[next.node]));
                }
            }
        }
        return D[end];
    }
}
 
class Node implements Comparable<Node>{
    int node, value;
    
    Node(int node, int value) {
        this.node = node;
        this.value = value;
    }
    
    @Override
    public int compareTo(Node e) {
        return value - e.value;
    }
}

 

처음에 여기서 다익스트라 실행할 때,

우선순위 큐에 넣고 해당 인덱스를 48번째 줄처럼 바로 방문 표시했었는데 (visited[start] = true;)

이상한 답이 나왔었다...

이렇게 나와서 굉장히 당황함..

 

그래서 저거 지워봤더니 결과값 잘 나옴💦💦

 

✅ 해결 아이디어
✔ 다익스트라 - BFS랑 유사. 우선순위 큐 사용

최단 경로 배열은 이렇게 나온다.

---

🔺 다른 풀이들

- 보니까 다익스트라 메소드 안에서 방문 배열 선언하고 초기화 해줘도 됨.

[BOJ] 백준 1916번 : 최소비용 구하기 (JAVA)

 

- 인접 행렬 사용하심 & 그래프에서 연결된 다음 정점들 방문할 때, Iterator 사용하심

[백준 1916번 최소비용 구하기] JAVA 풀이 (다익스트라)

 

- 과정 설명 굿 (복습용)

백준 1916번 : 최소비용 구하기 java

 

 

- Node 생성하지 않고, int[] 배열 만들어 푸심 & 우선순위 큐 오름차순 정렬도 람다식 사용

로그인

---

💬 느낀 점

이제 가중치 갖는 인접 리스트를 어찌저찌 혼자 작성할 줄 알게 되었다!

 

 

1회독	2회독	3회독	4회독	5회독
V	230522	230626	240518

---

(참고)

✔ 1753번: 최단 경로

[백준/JAVA] 1753번: 최단경로