- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
안녕하세요, 채점 서비스가 지원 되지 않은 문제라서 확실히 틀린 부분을 찾기 어려운 것 같습니다. 무엇보다 입력을 했는데 아무런 응답이 없어서 고민 후 글 올리게 되었습니다
우선 제 코드는
선생님 코드와 다른 점들이 있습니다. 참고는 했지만 이해가 안 가는 부분은 넣지 않았습니다.
1. 오름차순 정렬
2. Main class 의 dis[v] = 0;
혹시 오름차순을 한 이유와
바로 위해 pQ.offer(new Edge(v, 0));으로 v의 값을 0으로 초기화 해주었는데(제가 이해한게 틀렸을 가능성이 높습니다만,,ㅎㅎ) 또
dis[v] = 0;을 해준 이유가 궁금합니다.
그리고
어느 부분이 틀렸는지 알고싶습니다.
현재는 저렇게 코드 작성후 입력을 하면 아무런 결과/오류메세지가 나오지 않는 상황입니다.
네!
package ch09; import java.util.*; // 클래스 생성 : b,c 묶음 class Point { public int dot, cost; // 매개변수 있는 생성자 Point(int dot, int cost) { this.dot = dot; this.cost = cost; } } public class Dijkstra { static int[] arr; static ArrayList<ArrayList<Point>> graph; public void solution(int d) { // 우선순위 큐 생성 PriorityQueue<Point> pQ = new PriorityQueue<>(); // 인덱스1의 값을(0)을 tmp로 뽑아두고, 이를 기준으로 갱신 여부 판단 pQ.offer(new Point(d,0)); while(!pQ.isEmpty()) { Point tmp = pQ.poll(); int now = tmp.dot; int nowCost = tmp.cost; // 이미 최소비용일시 통과 = continue if(nowCost > arr[now]) continue; // 비용 확인 후 갱신 : a가 있는 배열로 들어가서 b,c확인 for(Point p : graph.get(now)) { if(arr[p.dot] > nowCost + p.cost) { // 갱신 후 최소비용으로 offer arr[p.dot] = nowCost + p.cost; pQ.offer(new Point(p.dot, nowCost + p.cost)); } } } } public static void main(String[] args) { Dijkstra T = new Dijkstra(); // 입력 2개 : 정점의 수(n), 간선의 수(m) Scanner kb = new Scanner(System.in); int n = kb.nextInt(); int m = kb.nextInt(); // m을 돌면서 출발정점(a), 도착정점(b), 최소비용(c) 입력 받기 // [배열 안의 배열] // 우선 a배열 생성을 위한 빈 껍데기 graph 선언 graph = new ArrayList<ArrayList<Point>>(); // n을 돌면서 a배열 생성 for(int i=0; i<=n; i++) { // 클래스를 사용하려면 new로 할당 graph.add(new ArrayList<Point>()); } for(int i=0; i<=m; i++) { int a = kb.nextInt(); int b = kb.nextInt(); int c = kb.nextInt(); graph.get(a).add(new Point(b,c)); } // 인덱스로 정점, 안의 값을 최소비용으로 하는 배열 하나 선언 // 초기화 : 최댓값, 여기서 인덱스는 0이 아닌 1부터 시작함 arr = new int[n+1]; Arrays.fill(arr, Integer.MAX_VALUE); // T.solution으로 1을 넘김 : 정점1부터 시작함 T.solution(1); // 출력 for(int i=2; i<=n; i++) { if(arr[i] != Integer.MAX_VALUE) System.out.println(i +":"+ arr[i]); else System.out.println(i +": impossible" ); } } }