https://www.acmicpc.net/problem/1504
1504번: 특정한 최단 경로
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존
www.acmicpc.net
#문제
방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.
세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.
#알고리즘
그래프 이론
다익스트라
#난이도
Gold 4
#풀이방법
그래프 이론...
그래프 이론을 이용한 알고리즘이 많고, 아마 알고리즘의 핵심요소 중 제일 큰 비중을 차지하지 않을까 생각된다.
풀이 방법은 다익스트라를 응용한 문제로서 복잡해 보이지만 단순하게만 생각하면 쉽게 풀 수 있는 문제이다.
( 이 풀이 방법을 보기 전 다익스트라 알고리즘을 미리 공부하고 보는 것을 추천한다)
보통 다익스트라 알고리즘은 특정 한 지점에서 목표 지점까지는 이동할 수 있는 최단거리를 구하는 것이다.
따라서 다익스트라 메소드를 따로 구현하여 인자값으로 처음 출발하는 노드값을 받고
그 값으로부터 N번 노드까지의 최단거리를 구해 배열을 반환하는 메소드를 구현하였다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | public static int[] dij(int[][] node,int v,int N) { int[] distance = new int[N+1]; boolean[] checked = new boolean[N+1]; distance[v] = 0; checked[v] = true; for(int i=1; i<N+1; i++) { if(!checked[i] && node[v][i] != 0) { distance[i] = node[v][i]; } } for(int a=0; a<N-1;a++) { int min = Integer.MAX_VALUE; int min_index = -1; for(int i=1; i<N+1;i++) { if(!checked[i] && distance[i] != Integer.MAX_VALUE) { if(distance[i] < min) { min = distance[i]; min_index = i; } } } checked[min_index] = true; for(int i=1; i<N+1; i++) { if(!checked[i] && node[min_index][i] != 0){ if(distance[i] > distance[min_index] + node[min_index][i]){ distance[i] = distance[min_index] + node[min_index][i]; } } } } return distance; }//인자 값으로 처음 출발하는 노드로부터 모든 노드까지의 최단거리를 반환해주는 메소드 | cs |
보통 여기까지가 우리가 흔히 알고 있는 다익스트라 알고리즘이다.
하지만 여기서 문제는 2개의 노드를 무조건! 거쳐야한다는 것이다.
그럼 여기서 생각해 볼 수 있는 경우의 수는 2가지이다.
반드시 거쳐야 하는 두 정점을 V1,V2라 가정하면
1. 첫번째 방법
1-> V1 -> V2 -> N
2. 두번째 방법
1 -> V2 -> V1 -> N
문제에서 요구하는 사항은 V1과 V2만 거치면 되는 것이지 순서는 상관 x
따라서 Math.min을 이용해 2가지의 중 최솟값을 구하여 출력해주면된다.
그럼 우리는 여기서 3개의 distance 배열이 필요하다.
1. dij 메소드에 1을 인자값으로 넣어 1 로부터 모든 노드에서의 최단거리를 구하는 distance1 array
2. dij 메소드에 V1을 인자값으로 넣어 V1 로부터 모든 노드에서의 최단거리를 구하는 distance2 array
3. dij 메소드에 V2를 인자값으로 넣어 V2로부터 모든 노드에서의 최단거리를 구하는 distance3 array
int sum = (int)Math.min(dis1[must_u]+dis2[must_v]+dis3[N] , dis1[must_v]+dis3[must_u]+dis2[N]);
하지만 여기서 큰 문제가 있다.!!!!
보통 우리가 배열로 노드를 구현 할때 거리가 무한정인 거리는 최댓값을 MAX인 Integer.MAX.VALUE로 놓고,
구현을 하는데 이렇게 할 경우, 오버플로우 가 발생하여 제대로 된 값을 출력하지 못해 틀림이 나온다..
그럼 어떻게 해야 하는가??
문제에서 제시하는 최대 노드의 갯수가 200,000이고 거리의 최댓값이 1,000이므로 아무리 많은 노드와 높은 간선을 다 더해도 200000*1000보다는 작다. 따라서 MAX 값을 integer의 최댓값이 아닌 200000000을 설정해야 정확한 값을
출력할 수 있다.
#코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 | import java.util.*; public class Main { static final int MAX = 200000000; public static int[] dij(int[][] node,int v,int N) { int[] distance = new int[N+1]; boolean[] checked = new boolean[N+1]; distance[v] = 0; checked[v] = true; for(int i=1; i<N+1; i++) { if(!checked[i] && node[v][i] != 0) { distance[i] = node[v][i]; } } for(int a=0; a<N-1;a++) { int min = Integer.MAX_VALUE; int min_index = -1; for(int i=1; i<N+1;i++) { if(!checked[i] && distance[i] != Integer.MAX_VALUE) { if(distance[i] < min) { min = distance[i]; min_index = i; } } } checked[min_index] = true; for(int i=1; i<N+1; i++) { if(!checked[i] && node[min_index][i] != 0){ if(distance[i] > distance[min_index] + node[min_index][i]){ distance[i] = distance[min_index] + node[min_index][i]; } } } } return distance; }//인자 값으로 처음 출발하는 노드로부터 모든 노드까지의 최단거리를 반환해주는 메소드 public static void main(String[] args) { Scanner sc = new Scanner(System.in); //방향성이 없는 그래프 int N = sc.nextInt();//정점의 개수 int[][] node = new int[N+1][N+1]; for(int i=1; i<N+1; i++) { for(int j=1; j<N+1; j++) { if(i == j){ continue; }//자기 자신의 경우는 넘어감 node[i][j] = MAX; } } int E = sc.nextInt();//간선의 개수 for(int i=0; i<E; i++) { int start = sc.nextInt(); int end = sc.nextInt(); int dis = sc.nextInt(); node[start][end] = dis; node[end][start] = dis; } int must_u = sc.nextInt();//반드시 거처야 하는 정점 Start int must_v = sc.nextInt();//반드시 거쳐야 하는 정점 end int[] dis1 = dij(node,1,N); //인자값을 1로 넣어 1에서부터 모든 노드로부터의 최단거리 int[] dis2 = dij(node,must_u,N); //인자값을 must_u를 넣어 must_u에서부터 모든 노드로부터의 최단거리 int[] dis3 = dij(node,must_v,N); //인자값을 must_v를 넣어 must_v에서부터 모든 노드로부터의 최단거리 int sum = (int)Math.min(dis1[must_u]+dis2[must_v]+dis3[N] , dis1[must_v]+dis3[must_u]+dis2[N] ); //1 -> must_u -> must_v -> N //1 -> must_v -> must_u -> N // 2가지 경우의 수에 최솟값 if(sum >= MAX) { System.out.println(-1); }//최댓값보다 클 경우 경로 존재 X, -1 출력 else System.out.println(sum); } } | cs |
'알고리즘 문제' 카테고리의 다른 글
| 백준 1254번) 팰린드롬 만들기 (JAVA) (0) | 2022.05.11 |
|---|---|
| 백준 1238번) 파티 (JAVA) (0) | 2022.05.03 |
| 백준 1074번) Z JAVA (0) | 2022.04.21 |
| 백준 1744번) 수 묶기 JAVA (0) | 2022.03.23 |
| 백준 1499번) 수리공 항승 JAVA (0) | 2022.03.17 |