[Java]백준 BaekJoon.AC 1753 : 최단경로 (다익스트라, 인접리스트 사용)

 

 

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

1753번: 최단경로

 

 

 

 

와, 대장정의 기록이다..

 

평소 시간초과나 메모리초과를 일으키는 함정은 없는지 돌다리를 두드리는 편이다.

근데 이 점에 몰두하다보면 브루트포스 같은 방식은 시도하기가 꺼려지더라.

브루트포스가 제일 나은 방법인데도 설마 아니겠지 싶은 생각에 사로잡혀 아이디어도 덜 떠오르고..

그래서 고작 몇 문제 쉬는 연습을 했더니... 덫에 걸린 것이다!ㅎㅎ

(변명의 시간이었다)

 

 

어쩐지 문제가 술술 잘 풀리고 재밌더라니.

실망시키지 않는 너란 존재...

채점까지 시도했다가 메모리 초과가 뜨길래 찾은 결론은 2차원배열이었다.

정점 2만개는 오바긴 했지ㅋㅋ...

 

눈물을 머금고 배열을 인접리스트로 바꿔주었다.

이렇게 멋찐 코드를 두고..ㅠㅠ

(이땐 내가 경솔했다.. 단번에 통과할 줄 알고 기대감에 미리 글을 작성하기 시작했거든.. 오류투성이 코드다)

 

-틀린 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int[][] arr;
	static boolean[] visit;
	static int INF = 10000;
	static int V, E, start;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	V = Integer.parseInt(st.nextToken());
    	E = Integer.parseInt(st.nextToken());
    	start = Integer.parseInt(br.readLine());
    	
    	arr = new int[V+1][V+1]; //0행렬은 제외
    	visit = new boolean[V+1];
    	
    	for(int i=1; i<V+1; i++) {
    		for(int k=1; k<V+1; k++) {
    			
    			arr[i][k] = INF;
    			if(i==k) arr[i][k] = 0;
    			
    		}
    	}
    	
    	for(int i=0; i<E; i++) {
    		int u, v, w;
    		
    		st = new StringTokenizer(br.readLine());
    		
    		u = Integer.parseInt(st.nextToken());
    		v = Integer.parseInt(st.nextToken());
    		w = Integer.parseInt(st.nextToken());
    			
    		arr[u][v] = w;
    		
    	}
    	
    	
    	visit[start] = true;
    	
    	while(true) {
    		int min = 100;
    		int n=-1;
    		
    		for(int i=1; i<V+1; i++) {
    			 if(arr[start][i]<min && !visit[i]) {
    				 min = arr[start][i];
    				 n = i;
    			 }
    		}
    		
    		if(min==100) {
    			break;
    		}else {
    			compare(min, n);
    		}

    	}
    	
    	for(int i=1; i<V+1; i++) {
    		if(arr[start][i]==INF) {
    			System.out.println("INF");
    		}else {
    			System.out.println(arr[start][i]);
    		}
    	}
    	
    	
	}
	
	public static void compare(int min, int n) {
		
		for(int i=1; i<V+1; i++) {
			if(arr[start][n] + arr[n][i] < arr[start][i]) {
				arr[start][i] = arr[start][n] + arr[n][i];
			}
		}
		
		visit[n] = true;
	}
}

 

 

 

 

그랬더니 이번엔 아예 틀렸다고 뜨더라.. 맞왜틀 연발하며 계속 고민하고 다른 코드까지 검색해봤다.

조금 다듬는쪽으로 수정을 했는데도 여전히 틀렸다고 떠서 질문들을 찾아보니

다익스트라 알고리즘을 구현하는 데에 치명적인 실수를 저질른 것이다.

 

 

이 글이 문제를 해결하는 데에 결정적인 도움이 됐다. 이 문제로 어려움을 겪고 있다면 이 글을 보자.

다익스트라를 더 깊이 이해할 수 있었다.

 

https://www.acmicpc.net/board/view/34516

글 읽기 - ★☆★☆★ [필독] 최단경로 (다익스트라 알고리즘) FAQ ★☆★☆★

 

 

PriorityQueue를 Node로 사용할 땐 반드시 우선순위 기준을 설정해줘야 한다.

이 경우에선 시작점으로부터 각 Node의 length 크기를 기준으로 뒀다.(작은순)

 

그리고 result 배열에 각 노드까지의 가중치를 저장했다.

 

그리고 계산 함수에선 if 비교문을 적절히 사용했다.

 

 

그리고... 아무리 고쳐줘도 틀렸다고 나오더라...ㅋㅋㅋㅋㅋ(해탈)

 

 

윗글을 정독하고 나서야 엄청난 오류를 범했음을 깨달았다.

INF 값을 너무 작게 줬던 것이다.

분명 나름의 근거를 이용해 1만으로 설정했던 것 같은데.

잘못을 인지한 후 다시 보니 이유를 도통 모르겠는 거다. 며칠만에 푼 문제라;

20만보다 큰 값으로 설정해야 함이 옳다.

 

 

고작 이 때문에 문제를 못풀었다 생각하면 콧바람이 쉭쉭 나오는데,

가만보면 얻은게 많은 문제다.

 

우선 Node를 연습할 수 있었다.

인접리스트마다 Node를 부여하는 건 처음 해봤다. 신기하고 재밌더라.

간단한 if문도 적용해보고, 모쪼록 완벽하게 깔끔한 코드라 생각하진 않지만 그런대로 완성했다.

 

신기한건 엉망으로 작성한 코드도 다듬다보면 인터넷에 올라와있는 코드와 점차 비슷해진다는 것이다..ㅋㅋ

따라하고 싶은 생각은 전혀 없었는데도 정답지와 가까운 해답이 나오는게 신기하다.

이래서 이걸 여기에 썼구나 하면서 수정 반복....

 

모쪼록 화내면서 코드 쓰다가도 정답 소식만 들으면 화가 풀리는 타입이라 기분이 그냥 좋다^^

 

 

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

public class Main {
	static PriorityQueue<Node> queue;
	static ArrayList<Node>[] list;
	static boolean[] visit;
	static int[] result;
	static int INF = 1000000;
	static int V, E, start;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	queue = new PriorityQueue<>();
    	
    	V = Integer.parseInt(st.nextToken());
    	E = Integer.parseInt(st.nextToken());
    	start = Integer.parseInt(br.readLine());
    	
    	list = new ArrayList[V+1]; //0행렬은 제외
    	visit = new boolean[V+1];
    	result = new int[V+1];
    	
    	Arrays.fill(result, INF);
    	
    	for(int i=1; i<V+1; i++) {
    		list[i] = new ArrayList<Node>();
    	}
    	
    	for(int i=0; i<E; i++) {
    		
    		st = new StringTokenizer(br.readLine());
    		
    		int u = Integer.parseInt(st.nextToken());
    		int v = Integer.parseInt(st.nextToken());
    		int w = Integer.parseInt(st.nextToken());
    			
    		list[u].add(new Node(v, w));
    		
    	}
    		
    	compare();
    	
    	StringBuilder sb = new StringBuilder();
    	for(int i=1; i<V+1; i++) {
    		int a = result[i];
    		sb.append(a == INF ? "INF" : a).append("\n");
    	}
    	
    	System.out.print(sb.toString());
	}
	
	public static void compare() {
		
		result[start] = 0;
		queue.add(new Node(start, 0));
		
		while(!queue.isEmpty()) {
			
			Node q = queue.poll();

			if(!visit[q.end]) {
				for(Node temp : list[q.end])
				if(result[q.end] + temp.length < result[temp.end]) {
					result[temp.end] = result[q.end] + temp.length;
					queue.add(new Node(temp.end, result[temp.end]));
				}
				visit[q.end] = true;
			}else{
				continue;
			}
		}	
	}
		
}

class Node implements Comparable<Node> {
	
	int end;
	int length;
	
	Node(int end, int length){
		this.end = end;
		this.length = length;
	}

	@Override
	public int compareTo(Node o) {
		
		return this.length-o.length;
	}
	
}