[Unsolved][JAVA] 백준 1753 최단경로

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

1753번: 최단경로

 

1. 서론

 

되게 전형적인 다익스트라 문제인데... 극악의 정답률을 보고 첫 번째로 놀랐고, 수억 번의 시간초과로 두 번 놀랐으나 결국 내가 부족한 사람이란 걸 깨달은 문제...

 

*다익스트라 문제 구별법

최단경로를 구해야 하는데 간선에 가중치가 있고 그 가중치가 자연수일 때

 

반응형

 

 

2. 문제 풀이

 

방향그래프가 입력으로 주어지고 시작점이 주어진다. 그 시작점을 기준으로 각각 나머지 정점에 도착했을 때 최단경로를 구하는 게 문제이다.

 

이렇게 간단한 문제인데 왜 저렇게 호들갑일까? 

 

1. 다익스트라라는 고급 알고리즘 기법

2. 문제 푸는 방향을 처음부터 잘못 잡았음

 

이유는 이정도 되시겠다.

다익스트라를 알지만 코드를 외우고 있지 않아서 뼈대 코드를 보면서 문제를 풀었다. 그 때문에 그 코드를 100% 이해하지 못하고 있었다. 그리고.... 모든 정점을 다 반복해야 하니까 정점 수만큼 반복해야겠네?라는 무식한 생각 때문에 반나절을 낭비하며 무한 시간초과 모드에 돌입하게 되었던 것이다.

 

다익스트라 알고리즘은 한 번만 돌려도 모든 정점을 방문하면서 최소 비용을 기록할 수 있다. 그래서 첫 번째로 정점 수만큼 돌린게 시간초과의 화근이었다. 그런데 그냥 다익스트라로는 통과는 했지만 시간이 너무 오래 걸렸다. 계속 시간초과를 보면서 어떻게 하면 시간이 초과되지 않지? 하고 찾아본 결과 다익스트라를 우선순위 큐로 구현하면 된다고 해서 우선순위 큐로 구현했더니 시간이 확 줄었다.

 

아래가 그냥 다익스트라 위에 우선순위 큐를 사용해 푼 코드이다.

 

문제 풀이 방법

 

1. 입력값을 받아 그래프를 만든다.

2. distance 배열을 만들고 입력받은 간선들을 돌면서 각 정점의 최소 경로를 갱신한다. => 다익스트라 알고리즘의 핵심

3. 문제의 조건에 맞게 각 정점에 따라 0, INF, 최소경로를 출력한다.

 

 

반응형

 

 

3. 코드 설명

 

-우선순위 큐 버전

 

import java.io.*;
import java.util.*;

public class Main {
	
	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 = new StringTokenizer(br.readLine());
		int v = Integer.parseInt(st.nextToken());
		int e = Integer.parseInt(st.nextToken());
		int start = Integer.parseInt(br.readLine());
		
		List<List<Vertex>> list = new ArrayList<>();
		for (int i = 0; i < v + 1; i++)
			list.add(new ArrayList<Vertex>());
		
		for (int i = 0; i < e; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			list.get(from).add(new Vertex(to, weight));
		}
        
      		//반복문 안에서 쓸 자원 생성
        	PriorityQueue<Vertex> pq = new PriorityQueue<>();
        	int[] distance = new int[v + 1];
        	boolean[] visit = new boolean[v + 1];
        	final int max = Integer.MAX_VALUE;
            
                //반복문 안에서 쓸 자원 초기화
                Arrays.fill(distance, max);
                distance[start] = 0;
                pq.offer(new Vertex(start, distance[start]));
                Vertex cur = null;
		
		while (!pq.isEmpty()) {
			cur = pq.poll();
			if (distance[cur.no] < cur.weight || visit[cur.no]) continue;
			visit[cur.no] = true;
			
			for (int i = 0; i < list.get(cur.no).size(); i++) {
				Vertex next = list.get(cur.no).get(i);
				if (distance[next.no] > distance[cur.no] + next.weight && !visit[next.no]) {
					distance[next.no] = distance[cur.no] + next.weight;
					pq.offer(new Vertex(next.no, distance[next.no]));
				}
			}
		}
		
		for (int i = 1; i <= v; i++)
			if (distance[i] == max) 
				System.out.println("INF");
			else
				System.out.println(distance[i]);
			
		bw.write(sb.toString());
		bw.close(); br.close();
	}
	
	static class Vertex implements Comparable<Vertex>{
		int no;
		int weight;
		
		public Vertex(int no, int weight) {
			this.no = no;
			this.weight = weight;
		}
		@Override
		public int compareTo(Vertex o) {
			return this.weight-o.weight;
		}

	}
}

 

Vertex란 Class를 선언했다. no는 도착하는 정점, weight는 가중치이다. 그리고 무게가 가벼운 순으로 정렬될 수 있게 해줬다.

그리고 이중리스트를 만들어서 출발하는 정점 안에 포함되는 Vertex들을 넣어줬다.

 

각 정점을 방문하기 위한 준비물들을 만들었다. 우선순위큐, 방문처리를 위한 visit, 가중치를 적기 위한 distance 배열을 선언했다.

그리고 최단경로 체크를 위해 초기값들을 전부 최댓값으로 저장해두고 큐에 출발 값을 넣어줬다.

그리고 탐색할 다음 정점을 찾으면서 방문하지 않았고 지금까지의 가중치와 다음경로의 가중치의 합이 다음 도착지의 가중치보다 작다면 그 값을 경신하며 최단 경로로 이동하고 그 값을 정점별로 저장하게 되는 것이다.

 

그리고 후에 distance 배열을 돌면서 정점별로 값을 출력해 준다.

 

오히려 시간초과가 많이 나서 다익스트라 개념을 다시 한번 복습하게 해 줘서 고맙다고 해야 하는지,, 뭔지 ㅋ