[JAVA]합리적인 이동경로(BOJ-2176[그래프,DP,다익스트라])

📂문제 설명

 

그래프의 한 정점 S에서 다른 한 정점 T로 이동하려 한다. 이동할 때 T에 가까워지며 이동하는 경우, 이를 합리적인 이동경로라 한다. 물론 이러한 경로는 최단경로가 아닐 수도 있다.

그래프가 주어졌을 때 가능한 합리적인 이동경로의 개수를 구하는 프로그램을 작성하시오. S=1, T=2 인 경우로 한다.

 

입력

첫째 줄에 정점의 개수 N(1<N≤1,000), 간선의 개수 M이 주어진다. 다음 M개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 길이 C(0 < C ≤ 10,000)인 간선으로 연결되어 있다는 의미이다. 두 정점은 최대 한 개의 간선으로만 연결될 수 있다. 간선은 방향성이 없다.

 

출력

첫째 줄에 답을 출력한다. 답은 2147483647을 넘지 않는다.

 

---

📂아이디어 및 알고리즘(문제 풀이)

• 문제 접근
  • 이번 문제에서는 최단 거리를 계산해야 하기 때문에 "다익스트라 알고리즘"을 알고 있어야 쉽게 접근할 수 있다.
  • DP로 합리적인 경로에 대한 count값을 구해줘야 한다.
  • 문제에 합리적인 이동 경로란?
    • A에서 B라는 정점으로 이동할 때 가까워지며 이동해야한다는 의미이다.
    • A->X->B 라는 경로가 100의 값이고 A->B 경로값이 50이라고 하면 무조건 A->B로만 가야한다.(최단 거리)
• 문제 풀이
  • 간선에 대한 정점과 길이 값을 Node값으로 하여 저장해준다. 이때 간선의 길이를 오름차순으로 자동 정렬하여 저장 할 수 있도록 한다.
  • ArrayList로 트리를 만들어 주고 입력한 간선의 정보를 Node로 묶어서 값을 넣어준다.
  • 초기의 dist[] 값은 Integer.MAX_VALUE 값을 넣어준다.
  • 다익스트라 함수 에서는 시작 노드의 Index값을 넣어주고 시작한다.
    • 초기 index값에 대한 count 값과 DP값인 dist값을 넣어준다.
    • 그리고 "우선순위 큐"에 추가하여 While문을 순회하도록 한다.
      • 현재 노드까지의 DP값(now.value)이 현재 DP값(dist[now.index])보다 크게 되면 넘어가준다.
      • 현재 index에서 연결된 next node값들을 순회하며 다음 dist[next.index]를 통해 비교하여 더 작은 값을 가지게 되면 dist[next.index]값을 업데이트해주고 "우선 순위 큐"에 넣어준다.
      • if(dist[next.index] < now.value)은 현재 index가 지나 왔던 노드(next.index)인 경우 지나왔던 count[next.index]값을 현재 노드(now.index)에 더해준다.
      • 이렇게 하면 지나왔던 곳의 count값을 계속 가져와서 최단거리에 대한 갯 수를 구할 수 있다.
  • 마지막으로 count[종점]값을 출력해 준다.

 

 

📂소스 코드

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
	static int dist[];
    static int[] count;
    static PriorityQueue<Node> pq = new PriorityQueue<>();
    
    static class Node implements Comparable<Node>{
  
    	int index;
    	int value;
    	
    	public Node(int index, int value) {
    		this.index=index;
    		this.value=value;
    	}
    	
    	@Override
    	public int compareTo(Node o) {
    		return value - o.value; 
    	}	
    }
    
	public static int dijkstra(ArrayList<ArrayList<Node>> list, int start) {
		count[start] = 1;
		dist[start] = 0;
		pq.add(new Node(start,0)); //시작 노드설정
		
		while(!pq.isEmpty()) {			
			Node now = pq.poll();
			if(now.value > dist[now.index]) {
				continue;
			}			
			for(Node next : list.get(now.index)) {
				if(dist[next.index] > dist[now.index] + next.value) {
					dist[next.index] = dist[now.index] + next.value;
					pq.add(new Node(next.index, dist[next.index]));
				}
				
				//자신이 왔던 노드로 다시 돌아가는 경우 그 count값을 자신에게 더해준다. 1->3 으로 왔을때
				//다시 3->1로 간 경우에 (이미 방문했던곳)을 갈 경우 거기의 count값을 누적 합 해준다. 
				if(dist[next.index] < now.value) {
					count[now.index] += count[next.index];
				}
			}	
		}
		return count[1];
	}
	

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		dist = new int[n+1];

		count = new int[n+1];
		
		ArrayList<ArrayList<Node>> list = new ArrayList<ArrayList<Node>>();
	
		for(int i=0;i<=n;i++) {
			list.add(new ArrayList<>());
			dist[i] = Integer.MAX_VALUE;
		}

		for(int i=0;i<m;i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			int z = sc.nextInt();
			list.get(x).add(new Node(y,z));
			list.get(y).add(new Node(x,z)); //가중치도 같이 저장해 둔다. 
		}
		
		int result = dijkstra(list,2);
		System.out.println(result);
	}

}

 

 

🔎출처

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

2176번: 합리적인 이동경로