[자바] 백준 1753 - 최단경로

다익스트라 때부터였던가요..? 제가 알고리즘을 포기한 게...

 

그래프와 연결된 기법 중에 가장 기초라고 하는데, 처음 다익스트라 문제 풀 때는 이해 안 가서 미치는 줄 알았다. 

대체 어떤 사람이길래 이런 생각을 하는 건지도 너무 신기했고.

근데 거의 3년만에 다익스트라 다시 보는데 지금도 이해가 안 간다 하핳하하

 

개념 되짚어 보려고 아래 블로그 참고했다.

bumbums.tistory.com/4

자바로 만드는 다익스트라 (dijkstra) 알고리즘

다익스트라는 시작점이 정해져있고, 해당 시작점에서 최단 경로로 목표점에 도달하는 문제에서 사용할 수 있다.

일단 시작점과 연결된 Node들을 찾아서 그 Node들과의 최단 거리를 거리 배열에 넣고, 

다시 그 Node와 연결된 다른 Node들을 찾아서 그 Node들과의 최단 거리를 찾는 행동을 반복한다.

 

대부분의 문제들은 노드와 간선의 개수를 몇십만개씩 줘서 연결 리스트로 푸는 게 괜히 마음이 편하다. 

 

1. Node 클라스 

- Edge라고도 많이 한다. 차이를 모르겠다.

 //정점에 관한 데이터를 담을 수 있는 Node Class 
	static class Node
	{
		int end;      //연결된 노드
		int dist;    //거리 
		Node link;
		
		public Node(int end, int dist)
		{
			super();
			this.end = end;
			this.dist = dist;
		}
	}

2. Vertex 클라스 

 //PriorityQueue 사용시, 우선순위를 지정해주기 위한 클라스
	//compareTo 메소드를 오버라이드 하여, 거리가 짧은 Vertex가 우선순위를 차지하도록 한다 
	static class Vertex implements Comparable<Vertex>
	{
		int end;
		int dist;
		
		public Vertex(int end, int dist)
		{
			super();
			this.end = end;
			this.dist = dist;
		}
		
		@Override
		public int compareTo(Vertex o) {
			return this.dist-o.dist;
		}
	}

3. main 메소드 

오 나름 잘 정리해놨었는데...?

 	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().trim().split(" ");
		StringBuilder sb = new StringBuilder();
		int V = Integer.parseInt(str[0]); //정점(Node)
		int E = Integer.parseInt(str[1]); 
		int K = Integer.parseInt(br.readLine().trim());
		
		Node[] node = new Node[V+1];
		Node newNode;
		int start, end, weight;
		
		//1. 그래프 생성 
		for(int e=0;e<E;e++) {
			str = br.readLine().trim().split(" ");
			
			start = Integer.parseInt(str[0]);
			end = Integer.parseInt(str[1]);
			weight = Integer.parseInt(str[2]);
			
			//새로운 정점 생성
			newNode = new Node(end, weight); 
			//node[start]에 연결되어 있던 기존 노드의 주소를 link에 담음
			newNode.link = node[start];      
			//node[start]에 새로 만든 newNode의 주소 담음 
			node[start] = newNode;
		}
		
		//2. 거리 배열, 방문 체크배열 
		//dist배열 : 시작점(K)에서 각 노드까지의 거리를 담은 배열 
		//우선은 MAX_VALUE로 채워준 뒤에 더 짧은 거리로 갱신한다
		int[] dist = new int[V+1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		boolean[] visited = new boolean[V+1];
		
		//3. 시작점 체크 
		dist[K] = 0;
		
		PriorityQueue<Vertex> que = new PriorityQueue<Vertex>();
		que.offer(new Vertex(K,0));
		
		Vertex vertex;
		Node currNode;
		int pos, min;
		
		while(!que.isEmpty()) {
			//2-2-c)에 이어서 : 이때 우선순위 큐이기 때문에, Vertex(2,2)가 먼저 뽑힌다. 
			vertex = que.poll();
			
			//현재의 위치 
			pos = vertex.start; 
			//현재 시작점에서 pos까지의 거리중 최단 거리가 담겨있다
			min = vertex.weight;
			
			if(visited[pos]) continue;
			visited[pos] = true;
			
			//1) 시작점(=1이라고 가정)을 기준으로 생각해보면
			//currNode에 node[1]에 붙어있는 첫 번째 노드를 담은 것
			currNode = node[pos];
			
			//2-1-a) 노드 1에는 노드 2와 노드 3이 연결되어 있는데, 나중에 입력된 노드가 
			//먼저 입력된 노드의 앞에 끼어들게 구현했으므로 일단 currNode에는
			//노드 3의 주소가 담겨 있다. 
			//2-3-a) 노드 2의 다음에 연결된 노드가 없어 currNode는 Null이 된다. 
			while(currNode!=null) {
				//2-1-b) next에는 3의 값이 입력되어 있고, nextWeight에는 거리 3
				//2-2-a) 이제 next에는 2의 값이 입력되어 있고, nextWeight에는 거리 2
				int next = currNode.connNode;
				int nextWeight = currNode.weight;
				//2-1-c) 한번도 노드 3을 방문한 적이 없고, dist[3]에는 현재 MAX_VALUE가 담겨있다
				//2-2-b) 한번도 노드 2를 방문한 적이 없고, dist[2]에는 현재 MAX_VALUE가 담겨있다 
				if(!visited[next] && min+nextWeight < dist[next] ) {
					dist[next] = min+nextWeight;
					//2-1-d) 이렇게 되면, que에는 Vertex(3,3)이 들어간다
					//2-2-c) 이렇게 되면, que에는 Vertex(2,2)가 들어간다.
					//이때 중요한 점은, que가 우선순위 큐이며, Vertex 클래스에서 
					//weight가 적은 값이 우선순위가 가지도록 구현했으므로 순서 상으로는 
					//Vertex(3,3)을 먼저 넣어도, 다음 순서에서 que.poll()을 할 때에는
					//Vertex(2,2)가 먼저 나온다. 
					que.offer(new Vertex(next,dist[next]));
				}
				
				//2-1-e) 노드 3에는 노드2의 주소가 담겨있다.이제 currNode에 노드2가 담겨있도록 한다. 
				//2-2-d) 노드 2 다음에는 연결된 노드가 없으므로 currNode = null이 된다
				currNode = currNode.link;
			}
		}
		for(int i=1;i<=V;i++) {
			if(dist[i]==Integer.MAX_VALUE) sb.append("INF\n");
			else sb.append(dist[i]+"\n");
		}
		System.out.println(sb.toString().trim());
	}

내가 처음 다익스트라를 배울 때도 그랬고, 지금도 간혹 헷갈리는 부분 중 하나는 visited 배열로 방문 여부를 체크하는 이유였다. 방문 여부를 체크하면 더 짧은 거리를 놓치는 게 아닌가 싶었다. 

예를 들어, 노드 1과 노드 5가 아래처럼 연결되어 있다고 하자.

노드 1 → 노드 5까지 가는 거리 : 5

노드 5 → 노드 1까지 가는 거리 : 2

 

만약 시작점이 노드 1이라서 일단 visited[1] = true 처리가 되었을 거고, que에는 Vertex(5,5)가 들어갈 텐데

que.poll()해서 Vertex(5,5)를 뽑았을 때, 이미 노드 1은 visited[1]=true 처리 되어 있어서, 훨씬 거리가 짧은 2가 고려되지 않는다. 

 

근데 내가 애초에 다익스트라의 전제를 모르고 있었기 때문에 든 의문이었다. 

다익스트라는 방향 그래프라는 전제를 깐 알고리즘 기법이다. 즉, 노드 1→노드 5와 노드 5→노드 1은 엄연히 다른 케이스다. 노드 5에서 노드 1로 갈 수 있다고 해서 항상 노드 1에서 노드 5로 갈 수 있는 건 아니다. 

위와 같은 상황에서 노드 1에서 노드 5로 갈 수 있는 방법은, 노드 1에서 노드 5로 바로 가는 것 뿐이다. 

 

정리하면, 노드 A, B, C가 있고, A→B로 가는 간선 1, A→C로 가는 간선, B→C로 가는 간선 3개가 있을 때, 노드 A에서 노드 C까지 가는 최단 거리는 다음과 같이 찾는다.

- 노드 A에서 노드 C까지의 현재 최단거리(dist[]배열의 값)

- 노드 A에서 노드 B까지 가는 최단 거리 + 노드 B에서 노드 C까지 가는 거리

위 두 개의 거리 중 가장 짧은 최단 거리를 선택하는 것 

간선의 가중치가 다음과 같다고 하자.

A→B로 가는 간선 : 1

A→C로 가는 간선 : 10

B→C로 가는 간선 : 2

 

시작 노드인 A에서 시작할 때, dist[B] = 1, dist[C] = 10으로 갱신될 것이고, 이제 노드 B와 노드 C를 차례로 들를텐데

노드 B에서 노드 C까지 가는 거리 = 2이므로 dist[C] = dist[B]+2 = 1+2 = 3으로 최단 거리가 갱신된다.