다익스트라 알고리즘 (수정 필요)

아래의 가중치 방향그래프에서 1번 정점에서 모든 정점으로의 최소 거리비용을 출력하는 프로 그램을 작성하세요. (경로가 없으면 Impossible를 출력한다)

 

▣ 입력설명

첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다.

그 다음부터 M줄에 걸쳐 연결정보와 거리비용이 주어진다.

 

▣ 출력설명

1번 정점에서 각 정점으로 가는 최소비용을 2번 정점부터 차례대로 출력하세요.

 

▣ 입력예제 

6 9

1 2 12 // 1번 정점에서 2번정점으로 가는데 12의 비용이 든다.

1 3 4

2 1 2

2 3 5

2 5 5

3 4 5

4 2 2

4 5 5

6 4 5

 

▣ 출력예제 

2 : 11

3 : 4

4 : 9

5 : 14

6 : impossible

 

---

 

다익스트라 알고리즘 : 

음의 가중치가 없는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다.

인접 행렬, 인접 리스트 둘 다 구현할 수 있는데 리스트가 효율적인 경우가 많기 때문에

인접 리스트로 구현하였습니다.

 

다익스트라 알고리즘의 경우 시간복잡도가 O(N)이므로 좀 더 효율적인 코드 구현을 위해 이 문제에서는

우선순위 큐 O(log N)으로 설명하겠습니다.

 

 

문제 이해 및 수도 코드 작성시 고려할 사항

 

고려 사항

 

 

수도 코드 작성

import java.util.*;

// 클래스 생성 : b,c 묶음

public class Dijkstra {
	// 우선순위 큐 생성
	// 인덱스1의 값을(0)을 tmp로 뽑아두고, 이를 기준으로 갱신 여부 판단

	public static void main(String[] args) {
		// 입력 2개 : 정점의 수(n), 간선의 수(m)
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		// m을 돌면서 출발정점(a), 도착정점(b), 최소비용(c) 입력 받기
		// 값을 인덱스1은 0, 나머지는 최댓값으로 초기화

	}

}

 

💡 내가 원하는 것 : 배열 안의 배열
    m 만큼을 돌면서 a,b,c를 입력 받는 것이 아니라
    a배열을 우선 만들고 a배열에 해당하는 b,c배열을 만들어서 넣는 것

 

public static void main(String[] args) {
		// 입력 2개 : 정점의 수(n), 간선의 수(m)
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		// m을 돌면서 출발정점(a), 도착정점(b), 최소비용(c) 입력 받기
		// [배열 안의 배열]
		// 우선 a배열 생성을 위한 빈 껍데기 graph 선언
		ArrayList<ArrayList<Point>> graph = new ArrayList<>();
		// 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));
		}

 

그 후 인덱스로 정점을 최소비용을 값으로 하는 배열 하나를 선언합니다.

값을 최댓값으로 초기화 한 후에, 출력하는 양식을 작성해보았습니다.

		// 인덱스로 정점, 안의 값을 최소비용으로 하는 배열 하나 선언
		// 초기화 : 값을 인덱스1은 0, 나머지는 최댓값, 여기서 인덱스는 0이 아닌 1부터 시작함
		int[] 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" );
		}

 

원래는 인덱스1의 값은 0으로 초기화 하려고 했으나, PriorityQueue에서 값을 0으로 초기화해서 offer()할 수 있기에 수정하였습니다.

// 클래스 생성 : b,c 묶음
class Point {
	public int dot, cost;
	
	// 매개변수 있는 생성자
	Point(int dot, int cost) {
		this.dot = dot;
		this.cost = cost;
	}
	
}

public class Dijkstra {
	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;
			// 비용 확인 후 갱신
		}
		
	}

 

코드 마지막 줄에서 arr[]이 사용되는 것을 알 수 있습니다.

따라서 int[] arr = new int[n+1]; 이 부분을 static으로 첫 줄에 선언해줍니다.

public class Dijkstra {
	static int[] arr;
	
	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;
			// 비용 확인 후 갱신
		}
		
	}

 

같은 이유로 graph도 static으로 선언해줍니다.

수정 전

			// 이미 최소비용일시 통과 = continue
			if(nowCost > arr[now]) continue;
			// 비용 확인 후 갱신 : a가 있는 배열로 들어가서 b,c확인
			for(Point p : graph.get(now)) {
				
			}

수정 후

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)) {
				
			}
			
		}
		
	}

 

최종 코드

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

	}

}

 

-- 현재 상황 22.03.28 --

입력값을 입력 해도 어떠한 결과나 오류 메세지가 나오지 않는 상황입니다. 

 

... 

 

Arrays클래스의 메소드 정리, 인접 리스트, 인접 행렬

 

 

 

참고 : https://bbangson.tistory.com/74

[Java] 다익스트라(Dijkstra) 알고리즘.