Problem 🔒
문제
https://www.acmicpc.net/problem/1504
방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.
세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.
출력
첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.
예제 입력 1
4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3
예제 출력 1
7
Approach 1 ⭕ - 다익스트라 3번
- 경로 구분
- 경로1 : 1번 정점 - v1 정점 - v2 정점 - N번 정점
- 경로2 : 1번 정점 - v2 정점 - v1 정점 - N번 정점
- 두 가지의 경로 중 최단 경로를 출력해야한다.
- 다익스트라(Dhstr 메서드)
- 시작 정점(int start)만 인자로 받는 다익스트라 함수를 만들었다.
- 먼저, 시작 정점의 비용을 0으로 초기화한다. (cost[start]=0)
- 방문하지 않은 비용배열(cost[])에서 가장 작은 비용을 가지고 있는 정점을 찾는다.
- 찾은 정점의 간선을 돌면서, 현재 최소비용보다 더 적다면 최소비용을 갱신한다.
- 최단 경로 구하기
- 1번 정점에서 시작하는 다익스트라 함수를 돌렸을때, 1번 정점 → v1 정점으로 가는 최단 경로, 1번 정점 → v2 정점으로 가는 최단 경로를 구할 수 있다.
- v1 정점에서 시작하는 함수를 돌렸을때, v1 → v2로 가는 최단 경로, v1 → N으로 가는 최단 경로를 구할 수 있다.
- v2 정점에서 시작하는 함수를 돌렸을때, v2 → N으로 가는 최단 경로, v2 → v1으로 가는 최단 경로를 구할 수 있다.
- 따라서, 3번의 다익스트라 함수를 실행하여 모든 경로의 최단 경로를 구할 수 있다.
- 출력
- 만약 그러한 경로가 없다면, 다익스트라 함수 실행 후 결과 값이 Integer.MAX_VALUE이다.
- 경로가 없다는 결과 값이 나온다면 해당 경로는 갈 수 없으므로 boolean 값을 false로 저장한다.
- 2가지 경로의 존재 여부에 따라 출력 코드를 작성했다.
Approach 2 ⭕ - 다익스트라 5번
Approach1에서는 많은 중복 코드와 불필요한 조건 및 변수가 많아서 리팩토링 해보았다.
그 과정에서 이전에는 다익스트라 함수를 3번 실행했다면, 5번으로 함수 호출이 증가하였다.
- 다익스트라 (Dhstr 메서드)
- 다익스트라 함수의 인자를 시작 정점(int start)과 도착 정점(int end) 2개를 입력받아, 경로가 없을 경우 -1을 반환하도록 처리하여 유효성 검사가 더 간결해졌다.
- 그리고 다익스트라 실행 전마다 방문배열과 비용배열을 초기화했다면, 다익스트라 함수 내에서 초기화하도록 중복코드를 수정하였다.
- 모든 정점에 방문했다면, 마지막에 도착 정점의 값(cost[end])을 반환하도록 수정하였다.
- 최단경로 결과 계산
- 이전에는 boolean 변수를 따로 선언하여 각각 경로의 유효성을 조건문으로 반복적으로 확인하여 불필요한 조건문이 많았다.
- 경로가 유효하지 않은 경우를 -1로 처리해 결과 계산을 간결하게 작성하였다.
다익스트라 함수를 적게 실행하는 것이 더 실행시간이 빠를 것 같았는데, 그 반대였다.
불필요한 조건문을 중복으로 확인하는 로직이 더 실행시간을 잡아먹는것 같다. ㅠㅠ
Solution 💡
다익스트라 3번(리팩토링 전)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
static int N, E, visit[], cost[];
static ArrayList<ArrayList<int[]>> list = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken())+1; E = Integer.parseInt(st.nextToken());
visit=new int[N]; cost=new int[N];
for(int i=0; i<N; i++){cost[i]=Integer.MAX_VALUE; list.add(new ArrayList<>());}
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 c = Integer.parseInt(st.nextToken());
list.get(u).add(new int[]{v,c});
list.get(v).add(new int[]{u,c});
}
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
//case1 : 1-v1-v2-N 순으로 방문
//case2 : 1-v2-v1-N 순으로 방문
boolean case1 = true; // 경로가 있는지 확인
boolean case2 = true; // 경로가 있는지 확인
Dhstr(1);
int oneTov1 = cost[v1]; if(oneTov1 == Integer.MAX_VALUE) case1=false;
int oneTov2 = cost[v2]; if(oneTov2 == Integer.MAX_VALUE) case2=false;
// 방문배열, 비용배열 초기화
for(int i=0; i<N; i++){cost[i]=Integer.MAX_VALUE; visit[i]=0;}
Dhstr(v1);
int v1Tov2 = cost[v2]; if(v1Tov2 == Integer.MAX_VALUE) case1=false;
int v1ToN = cost[N-1]; if(v1ToN == Integer.MAX_VALUE) case2=false;
// 방문배열, 비용배열 초기화
for(int i=0; i<N; i++){cost[i]=Integer.MAX_VALUE; visit[i]=0;}
Dhstr(v2);
int v2ToN = cost[N-1]; if(v2ToN == Integer.MAX_VALUE) case1=false;
int v2Tov1 = cost[v1]; if(v2Tov1 == Integer.MAX_VALUE) case2=false;
int ans = -1;
if(case1 && case2){
ans = Math.min(oneTov1+v1Tov2+v2ToN, oneTov2+v1ToN+v2Tov1);
}else if(case1){
ans = oneTov1+v1Tov2+v2ToN;
}else if(case2){
ans = oneTov2+v1ToN+v2Tov1;
}
System.out.println(ans);
}
public static void Dhstr(int start){
cost[start] = 0;
while (true){
int next = -1; // 다음에 방문할 노드 번호
int d = Integer.MAX_VALUE; // 최소비용
for(int i=1; i<N; i++){
if(visit[i]==0 && cost[i]<d){next = i; d = cost[i];} // 다음에 방문할 노드 찾기
}
if(next==-1) break; // 더 이상 방문할 노드가 없음
visit[next] = 1; // 방문 처리
for(int[] i : list.get(next)){
// 현재 최소비용보다 비용이 더 적다면 최소비용 갱신
if(cost[next]+i[1] < cost[i[0]]){
cost[i[0]] = cost[next]+i[1];
}
}
}
}
}
다익스트라 5번(리팩토링 후)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class 특정한최단경로 {
static int N, E, visit[], cost[];
static ArrayList<ArrayList<int[]>> list = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken())+1; E = Integer.parseInt(st.nextToken());
visit=new int[N]; cost=new int[N];
for(int i=0; i<N; i++){cost[i]=Integer.MAX_VALUE; list.add(new ArrayList<>());}
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 c = Integer.parseInt(st.nextToken());
list.get(u).add(new int[]{v,c});
list.get(v).add(new int[]{u,c});
}
st = new StringTokenizer(br.readLine());
int v1 = Integer.parseInt(st.nextToken());
int v2 = Integer.parseInt(st.nextToken());
//case1 : 1-v1-v2-N 순으로 방문
//case2 : 1-v2-v1-N 순으로 방문
int case1 = -1, case2 = -1;
int a1 = Dhstr(1,v1), a2 = Dhstr(v1,v2), a3 = Dhstr(v2,N-1),
b1 = Dhstr(1,v2), b3 = Dhstr(v1,N-1);
if(a1>=0 && a2>=0 && a3>=0) case1 = a1+a2+a3;
if(b1>=0 && a2>=0 && b3>=0) case2 = b1+a2+b3;
System.out.println(case1!=-1&&case2!=-1?Math.min(case1, case2):Math.max(case1, case2));
}
public static int Dhstr(int start, int end){
// 방문배열, 비용배열 초기화
for(int i=0; i<N; i++){cost[i]=Integer.MAX_VALUE; visit[i]=0;}
cost[start] = 0;
while (true){
int next = -1; // 다음에 방문할 노드 번호
int d = Integer.MAX_VALUE; // 최소비용
for(int i=1; i<N; i++){
if(visit[i]==0 && cost[i]<d){next = i; d = cost[i];} // 다음에 방문할 노드 찾기
}
if(next==-1) break;
visit[next] = 1; // 방문 처리
for(int[] i : list.get(next)){
// 현재 최소비용보다 비용이 더 적다면 최소비용 갱신
if(cost[next]+i[1] < cost[i[0]]){
cost[i[0]] = cost[next]+i[1];
}
}
}
return cost[end]==Integer.MAX_VALUE?-1:cost[end];
}
}
'코딩 테스트(Coding Test) > 백준' 카테고리의 다른 글
[백준] 1753번 : 최단경로 - 자바(Java) (1) | 2024.11.22 |
---|---|
[백준] 1238번 : 파티 - 자바(Java) (1) | 2024.11.22 |
[백준] 2260번 : 회장 뽑기 - 자바(Java) (0) | 2024.11.19 |
[백준] 1967번 : 트리의 지름 - 자바(Java) (1) | 2024.11.18 |
[백준] 1167번 : 트리의 지름 - 자바(Java) (0) | 2024.11.16 |