백준 1753: 최단경로 (다익스트라 알고리즘) -Java

골드4

https://www.acmicpc.net/problem/175

---

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

---

입력 값

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

출력 값

0
2
3
7
INF

자바 코드

package practice;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	// 연결된 다음 노드에 대한 정보
	static class Node {
		int nextNode; // 다음 노드 번호
		int weight; // 다음 노드까지 가는 간선의 가중치
		
		public Node(int nextNode, int weight) {
			this.nextNode = nextNode;
			this.weight = weight;
		}
	}
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	int totalNode = Integer.parseInt(st.nextToken()); // 정점(node)의 개수
    	int totalEdge = Integer.parseInt(st.nextToken()); // 간선(edge)의 개수
    	
    	int startNode = Integer.parseInt(br.readLine()); // 최단경로를 구할 시작 Node
    	
    	// 각 노드와 노드의 간선, 가중치를 표현한 graph를 배열로 선언 (리스트를 값으로 가지는 사실상 2차원 배열)
    	List<Node>[] graph = new ArrayList[totalNode + 1];
    	// 시작 노드에서 각 노드까지의 최단경로들 (index가 노드 번호)
    	int[] resultList = new int[totalNode + 1];
    	
    	
    	/**
    	 * 1. graph를 리스트(노드 보관용)로 초기화 -> Arrays.fill()로 채우기 
    	 * 2. graph의 index가 노드 번호가 되며 해당 인덱스 값(리스트)에 NextNode 추가 (연결되는 노드) 
    	 */
    	/*
    	Arrays.fill(graph, new ArrayList<NextNode>()); 
    	
    	// 최단 경로를 찾는 것임으로 이 배열에 넣고 비교하기 위해 우선 최댓값으로 초기화
    	Arrays.fill(resultList, Integer.MAX_VALUE); 
    	*/
    	
    	// 초기화
        for (int i = 1; i <= totalNode; i++) {
        	graph[i] = new ArrayList<>(); 
            resultList[i] = Integer.MAX_VALUE; //최대값으로 초기화, 최단거리를 찾기 위함.    
        }
	    
    	boolean[] visitNode = new boolean[totalNode + 1]; //0번째 인덱스는 사용안하므로 +1 하여 사이즈 설정
    	
    	for (int i=0; i<totalEdge; i++) {
    		st = new StringTokenizer(br.readLine());
    		int u = Integer.parseInt(st.nextToken()); // 노드 번호
    		int v = Integer.parseInt(st.nextToken()); // 다음 노드
    		int w = Integer.parseInt(st.nextToken()); // 다음 노드까지가는 간선의 가중치
    		
    		graph[u].add(new Node(v, w));
    	}
    	
    	dijkstra(startNode, graph, resultList, visitNode);
    }
    
	public static void dijkstra(int startNode, List<Node>[] graph, int[] resultList, boolean[] visitNode) {
		//NextNode를 넣는 우선순위 큐 선언 -> 내부는 NextNode의 weight 값을 기준으로 오름차순 정렬
		PriorityQueue<Node> queue = new PriorityQueue<>((node1, node2) -> node1.weight - node2.weight); 
		
		queue.add(new Node(startNode, 0)); //시작 노드, 자기 자신까지의 거리는 0
		resultList[startNode] = 0; 
		
		// 큐가 빌 때까지 반복
		while (!queue.isEmpty()) {
			Node nowNode = queue.poll(); // 가장 짧은 가중치를 가진 노드 꺼내기
			
			// 현재 노드의 다음 노드 방문 처리
			if (!visitNode[nowNode.nextNode]) {
				visitNode[nowNode.nextNode] = true;
			}
			
			List<Node> nextNodeList = graph[nowNode.nextNode]; // 현재 노드에 연결된 다음 노드 리스트

			// 다음 노드까지의 가중치를 더하여 짧은 것을 결과목록에 추가
			for (Node nextNode: nextNodeList ) {
				// 결과 목록의 최단 경로값 vs 다음 노드까지의 누적 가중치 -> 비교하여 누적 가중치가 더 낮다면 최단 경로 값 최신화
				if (!visitNode[nextNode.nextNode] && resultList[nextNode.nextNode] > nowNode.weight + nextNode.weight) {
					resultList[nextNode.nextNode] = nowNode.weight + nextNode.weight;
					//최신화에 성공했다면, 또 연결된 다음 노드까지의 값을 비교하기 위해 큐에 추가한다.  
					queue.add(new Node(nextNode.nextNode, resultList[nextNode.nextNode])); 
				}
			}
			
		}
		
		// 결과 값 출력
		for (int i=1; i<resultList.length; i++) {
			System.out.println(resultList[i] == Integer.MAX_VALUE ? "INF" : resultList[i]);
		}
		
	}    
}

 

 

---

코드 상세

// 연결된 다음 노드에 대한 정보
static class Node {
	int nextNode; // 다음 노드 번호
	int weight; // 다음 노드까지 가는 간선의 가중치
	
	public Node(int nextNode, int weight) {
		this.nextNode = nextNode;
		this.weight = weight;
	}
}

Node 클래스

각 노드의 역할을 할 Node 클래스.

nextNode 는 연결된 다음 노드의 번호, weight은 해당 간선의 가중치 값이다.

 

// 각 노드와 노드의 간선, 가중치를 표현한 graph를 배열로 선언 (리스트를 값으로 가지는 사실상 2차원 배열)
List<Node>[] graph = new ArrayList[totalNode + 1];
// 시작 노드에서 각 노드까지의 최단경로들 (index가 노드 번호)
int[] resultList = new int[totalNode + 1];
    	
// 초기화
for (int i = 1; i <= totalNode; i++) {
	graph[i] = new ArrayList<>(); 
	resultList[i] = Integer.MAX_VALUE; //최대값으로 초기화, 최단거리를 찾기 위함.
}
	    
boolean[] visitNode = new boolean[totalNode + 1]; //0번째 인덱스는 사용안하므로 +1 하여 사이즈 설정

graph

문제에 등장하는 방향 그래프 역할을 할 ArrayList<Node>로 이루어진 배열. 배열의 각 인덱스가 노드의 번호를 의미한다.

(0번 인덱스는 생략)

한 노드에 연결된 노드는 여러개 일 수 있으므로, 배열의 원소는 ArrayList<Node>로 둔다. 

 

resulstList

시작노드부터 각 노드까지의 최단경로를 기록할 배열, 역시 각 인덱스가 노드의 번호를 의미한다.

 

visitNode

각 노드의 방문 여부를 기록할 boolean 배열.

public static void dijkstra(int startNode, List<Node>[] graph, int[] resultList, boolean[] visitNode) {
	//NextNode를 넣는 우선순위 큐 선언 -> 내부는 NextNode의 weight 값을 기준으로 오름차순 정렬
	PriorityQueue<Node> queue = new PriorityQueue<>((node1, node2) -> node1.weight - node2.weight); 
	
	queue.add(new Node(startNode, 0)); //시작 노드, 자기 자신까지의 거리는 0
	resultList[startNode] = 0; 
		
	// 큐가 빌 때까지 반복
	while (!queue.isEmpty()) {
		Node nowNode = queue.poll(); // 가장 짧은 가중치를 가진 노드 꺼내기
			
		// 현재 노드의 다음 노드 방문 처리
		if (!visitNode[nowNode.nextNode]) {
			visitNode[nowNode.nextNode] = true;
		}
			
		List<Node> nextNodeList = graph[nowNode.nextNode]; // 현재 노드에 연결된 다음 노드 리스트

		// 다음 노드까지의 가중치를 더하여 짧은 것을 결과목록에 추가
		for (Node nextNode: nextNodeList ) {
			// 결과 목록의 최단 경로값 vs 다음 노드까지의 누적 가중치 -> 비교하여 누적 가중치가 더 낮다면 최단 경로 값 최신화
			if (!visitNode[nextNode.nextNode] && resultList[nextNode.nextNode] > nowNode.weight + nextNode.weight) {
				resultList[nextNode.nextNode] = nowNode.weight + nextNode.weight;
				//최신화에 성공했다면, 또 연결된 다음 노드까지의 값을 비교하기 위해 큐에 추가한다.  
				queue.add(new Node(nextNode.nextNode, resultList[nextNode.nextNode])); 
			}
		}
			
	}
		
	// 결과 값 출력
	for (int i=1; i<resultList.length; i++) {
		System.out.println(resultList[i] == Integer.MAX_VALUE ? "INF" : resultList[i]);
	}
		
}

 

dijkstra 함수

다익스트라 알고리즘을 수행할 함수.

 

1. 첫 번째로 검사할 노드의 값(시작 노드)을 우선순위큐에 넣는다. (다음 노드 번호=1, 가중치 = 0)
    -> 자기 자신까지의 거리이므로 해당 노드에 대한 최단 경로를 0으로 설정한다. -> resultList[startNode] = 0;

2. 이제 큐가 빌 때 까지 반복하는데, 우선 가장 가중치가 작은 노드를 꺼낸다.

3. 해당 노드의 다음 노드 번호를 방문 처리한다. 

    -> visitNode[nowNode.nextNode] = true; 

3. 해당 노드의 다음 노드 번호(nextNode)로 graph에서 연결된 노드 목록을 찾는다.
    ->  다음 노드 번호가 graph의 index가 되고, 해당 index의 값들이 다음 노드 목록이다.

4. 다음 노드 목록들을 반복하며 가중치를 합하여, 해당 노드의 현재 최단 경로 값과 비교 후 더 작다면 최신화한다.

5. 최신화에 성공한 노드 번호와 누적된 가중치로 Node를 생성하여 큐에 추가한다. 

    -> 다시 2로 가며 반복.

 

 

 

PS

계속 잘못된 최단 경로 값이 출력되어 애를 먹었는데, 디버깅을 해보니 graph 값이 잘못되어있었다.

graph 내 모든 List에 값(노드)이 채워져있었고, 알고보니 ArrayList.fill() 을 활용해 간단하게 초기화하려던 것이 화근이었다. graph 배열 내 각각 다른 List 객체들로 채워져야하는데, 하나의 주소를 참조하는 같은 객체로 초기화해버렸던 것이다. 입력 값을 받아 노드 번호에 해당하는 index의 List에 채운다해도, 모두 같은 주소를 참조하는 같은 객체이기에 같은 List에 노드 값을 추가해버렸다.