[백준 1753] 최단경로 (java)

문제보러가기

1753번: 최단경로

이문제는 다익스트라의 기본이 되는 문제였다. 알고리즘을 알고는 있었지만 문제를 풀어본 적이 없는 것 같아 기초 문제부터 시작! 

 

 

 

 

 

 

문제풀이

-각 노드의 간선 정보를 저장할 list와 출발 노드부터 해당 노드까지의 최소거리를 갱신해주는 배열 dist []를 선언한다.

-list의 경우 노드 숫자만큼의 배열과 각 노드의 연결된 노드와 가중치의 정보를 저장할 수 있도록 List <Point 2> list []로 선언해 준다. * Point 2는 노드와 가중치 정보 클래스

 

-다익스트라 알고리즘의 경우 현재 노드로 올 수 있는 최단경로를 dist []에 갱신하면서 정보를 저장하게 된다. 그러므로 처음 초기화는 큰 값인 INF로 초기화를 해놔야 한다.

-가는 경로가 여러 개일 경우 작은 것을 골라야 하므로 PriorityQueue를 사용하여 오름차순으로 사용한다.

-이미 방문했던 노드의 경우 check [] 배열을 통해 걸러준다.

 

-주어진 테스트 케이스의 dist 배열은 이런 식으로 진행이 된다

테스트 케이스의 방향 그래프

* 현재 노드가 1일 때 (start노드) : 이 노드 기준으로 다른 노드들의 경로 값을 계산한 걸 배열에 저장하게 된다.

* 1과 연결된 노드로 가는 값을 계산하여 더 작을 경우 넣어준다. 초기값이 INF였으므로 당연히 갱신된다.

1	2	3	4	5
0	2	3	INF	INF

* 현재 노드가 2일 때 - > PriorityQueue에서 꺼낸 것

* 3의 경우 1->3 , 1->2->3이 다 가능하다 그중 최솟값으로 갱신 : dist [3] < dist [2] + 2에서 3으로 가는 가중치 이므로 dist [3]은 갱신하지 않고 넘어가는 것

1	2	3	4	5
0	2	3	7	INF

* 현재 노드가 3일 때

* 4의 경우 1->2->4 , 1->3->4 , 1->2->3->4 경로가 가능하다. 1->2->4  이 경우를 이미 탐색하여 dist [4]에 저장했고, 이것과 다른 경로와 비교했을 때 최솟값이었으므로 갱신하지 않는다.

1	2	3	4	5
0	2	3	7	INF

* 현재 노드가 4일 때

1	2	3	4	5
0	2	3	7	INF

->이런 식으로 배열이 변경되면서 시작 노드부터의 최소 경로 값이 담기게 된다.

->예 : dist [3] == 1번 노드에서 3번 노드까지 갈 수 있는 경로중 가장 최단거리

 

-5의 경우 1부터 갈 수 있는 경로가 없으므로 초기값인 INF를 출력한다.

 

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	private static final int INF = Integer.MAX_VALUE;
    static List<Point2> list[];
    static int dist[];
    static boolean check[];

	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int v = Integer.parseInt(st.nextToken());
		int e = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[v + 1];
		dist = new int[v+1];
		check = new boolean[v+1];
		
		 Arrays.fill(dist, INF);
		 for(int i=0;i<list.length;i++) {
			 list[i] = new ArrayList<>();			
		 }
		st = new StringTokenizer(br.readLine());
		int k =Integer.parseInt(st.nextToken());
		for(int i=0;i<e;i++) {
			st = new StringTokenizer(br.readLine());
			int startV = Integer.parseInt(st.nextToken());
			int endV = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			//방향 그래프이므로 한쪽만 추가를 해줌
			list[startV].add(new Point2(endV,w));

		}
        //시작점부터의 각 노드까지의 경로값을 다익스트라 알고리즘을 이용해 dist채움
		dijkstra(k);
		for(int i=1;i<list.length;i++) {
			if(dist[i]==INF)
				bw.append("INF\n");
			else
				bw.append(String.valueOf(dist[i])+"\n");
		}
		bw.flush();
		
	}
	static void dijkstra(int start){
		
        PriorityQueue<Point2> queue = new PriorityQueue<>();
        queue.add(new Point2(start, 0));
        //시작점은 0으로 지정
        dist[start] = 0;

        while (!queue.isEmpty()){
            Point2 curPoint = queue.poll();
            int curNode = curPoint.end;

            if(check[curNode] == true) continue;
            check[curNode] = true;

			//현재노드에서 갈 수 있는 노드들을 다 탐색
            for(int i = 0; i < list[curNode].size(); i++){
                Point2 nextNode = list[curNode].get(i);

                //기존의 경로보다 새로운 경로가 작을 경우
                if(dist[nextNode.end] > dist[curNode] + nextNode.weight){
                    dist[nextNode.end] = dist[curNode] + nextNode.weight;
                    queue.add(new Point2(nextNode.end, dist[nextNode.end]));
                }
            }

        }

    }

}
class Point2 implements Comparable<Point2>{
    int end;
    int weight;

    public Point2(int end, int weight){this.end = end; this.weight = weight;}

    @Override
    public int compareTo(Point2 o) {
    	//오름차순
        return weight - o.weight;
    }
}