입력했을 시 오류 메세지가 나오지 않아 찾기 어렵습니다.

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

5. 다익스트라 알고리즘(채점지원안됨)

작성

224

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! 
- 먼저 유사한 질문이 있었는지 검색해보세요. 
- 서로 예의를 지키며 존중하는 문화를 만들어가요. 
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.

안녕하세요, 채점 서비스가 지원 되지 않은 문제라서 확실히 틀린 부분을 찾기 어려운 것 같습니다. 무엇보다 입력을 했는데 아무런 응답이 없어서 고민 후 글 올리게 되었습니다

우선 제 코드는

선생님 코드와 다른 점들이 있습니다. 참고는 했지만 이해가 안 가는 부분은 넣지 않았습니다.

1. 오름차순 정렬

2. Main class 의 dis[v] = 0;

혹시 오름차순을 한 이유와

바로 위해 pQ.offer(new Edge(v, 0));으로 v의 값을 0으로 초기화 해주었는데(제가 이해한게 틀렸을 가능성이 높습니다만,,ㅎㅎ) 또

dis[v] = 0;을 해준 이유가 궁금합니다.

그리고

어느 부분이 틀렸는지 알고싶습니다.

현재는 저렇게 코드 작성후 입력을 하면 아무런 결과/오류메세지가 나오지 않는 상황입니다.

코테 준비 같이 해요! java

답변 1

김태원

지식공유자

안녕하세요^^

제가 실행해볼수 있게 복사붙여넣기가 되는 텍스트 형태로 코드를 올려주세요.

hwanghsp

질문자

네!

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" );
		}
		

	}

}

인프런 커뮤니티 질문&답변

입력했을 시 오류 메세지가 나오지 않아 찾기 어렵습니다.