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

루돌프친구

작성한 질문수

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

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

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

작성

242

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

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

우선 제 코드는

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

1. 오름차순 정렬

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

혹시 오름차순을 한 이유와

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

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

그리고

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

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

코테 준비 같이 해요! java

퀴즈

회의실 배정 문제에서 최대 회의 수를 얻기 위해 회의를 정렬하는 주요 기준은 무엇일까요?

시작 시간 오름차순

종료 시간 오름차순

회의 시간 길이 오름차순

종료 시간 내림차순

답변 1

김태원

지식공유자

안녕하세요^^

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

루돌프친구

질문자

네!

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

	}

}

루돌프친구

작성한 질문수

전체 Q&A

질문하기