최초 코드 - DFS풀이 (정확성: 100, 효율성: 0)
class Solution {
private int answer= Integer.MAX_VALUE;
private int temp = Integer.MAX_VALUE;
private int[][] adj;
private boolean[] visited;
public int solution(int n, int s, int a, int b, int[][] fares) {
//adj생성 0번행,0번열은 무시
adj = new int[n+1][n+1];
visited = new boolean[n+1];
for(int[] fare: fares){
int n1 = fare[0];
int n2 = fare[1];
int f = fare[2];
adj[n1][n2]=f;
adj[n2][n1]=f;
}
//1) 따로가는 경우 계산
answer = Math.min(answer,calcMinCost(s,a)+calcMinCost(s,b));
//2) 각 지점까지만 합승하고 이후 따로가능 경우 계산
for(int i=1; i<=n; i++){
answer = Math.min(answer, calcMinCost(s, i) + calcMinCost(i, a) + calcMinCost(i, b));
}
return answer;
}
private int calcMinCost(int start, int dst){
dfs(start, dst, 0);
int result = temp;
temp = Integer.MAX_VALUE;
visited = new boolean[adj.length+1];
return result;
}
private void dfs(int start, int dst, int sumCost){
//도착 시
if(start==dst){
//todo 계산한 cost어떻게 처리할지 -> 일단 temp
temp = Math.min(temp, sumCost);
return;
}
for(int i=1; i<adj.length; i++){
//최초 호출 시 방문처리가 안돼있기 때문에 해당 코드 실행, 호출 전 방문처리되어 있어도 상관없어서 이렇게 해도 됨.
visited[start] = true;
if(adj[start][i]!=0&&!visited[i]){
visited[i]=true;
dfs(i, dst, sumCost+adj[start][i]);
visited[i]=false;
}
}
}
}
다익스트라의 개념을 모르고 무작정 완전탐색으로 풀었을 때의 코드이다.
효율성도 같이 요구하는 문제이기에 통과하지 못했다.
두번째 코드 - 다익스트라 풀이 (정확성: 100, 효율성: 75)
import java.util.*;
class Solution {
private int[][] adj;
private int res;
private int[] minCost;
private boolean[] visited;
private int n;
public int solution(int _n, int s, int a, int b, int[][] fares) {
//자주 쓰이는 n을 전역으로 변경
n=_n;
//1. 인접 행렬 생성
adj = new int[n+1][n+1];
for(int[] fare: fares){
int n1 = fare[0];
int n2 = fare[1];
int weight = fare[2];
adj[n1][n2] = weight;
adj[n2][n1] = weight;
}
//2. 합승하지 않은 요금 계산
// s->a, s->b도 다익스트라
res = dijkstra(s, a) + dijkstra(s, b);
//3. s를 제외한 모든 정점에서 a까지 최단거리 + b까지 최단거리 + s->i까지 최단거리
for(int i=1; i<n+1; i++){
if(i==s){
continue;
}
res = Math.min(res, dijkstra(s, i) + dijkstra(i, a) + dijkstra(i, b));
}
return res;
}
private int dijkstra(int departure, int destination){
if(departure == destination){
return 0;
}
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(departure, 0));
init(departure);
while(!pq.isEmpty()){
Node current = pq.poll();
if(visited[current.end]){
continue;
}
visited[current.end]=true;
for(int i=1; i<n+1; i++){
int nextWeight = adj[current.end][i];
if(nextWeight == 0){
continue;
}
if(!visited[i] && minCost[i]> current.weight + nextWeight){
minCost[i] = current.weight + nextWeight;
pq.offer(new Node(i, minCost[i]));
}
}
}
return minCost[destination];
}
private void init(int departure){
minCost = new int[n+1];
Arrays.fill(minCost, Integer.MAX_VALUE);
minCost[departure] = 0;
visited = new boolean[n+1];
}
class Node implements Comparable<Node>{
int end;
int weight;
Node(int end, int weight){
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Node o){
return this.weight - o.weight;
}
}
}다익스트라 유형을 접한 후 적용해서 푼 코드이다. 효율성 75점을 받은 최적화되지 못한 코드이다.
최종 코드
import java.util.*;
class Solution {
private int[][] adj;
private int res=Integer.MAX_VALUE;
private int[] minCost;
private boolean[] visited;
private int N;
public int solution(int n, int s, int a, int b, int[][] fares) {
N=n;
//1. 인접 행렬 생성
adj = new int[N+1][N+1];
for(int[] fare: fares){
int n1 = fare[0];
int n2 = fare[1];
int weight = fare[2];
adj[n1][n2] = weight;
adj[n2][n1] = weight;
}
int[] startS = dijkstra(s);
int[] startA = dijkstra(a);
int[] startB = dijkstra(b);
for(int i=1; i<N+1; i++){
res = Math.min(res, startS[i]+startA[i]+startB[i]);
}
return res;
}
private int[] dijkstra(int departure){
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(departure, 0));
init(departure);
while(!pq.isEmpty()){
Node current = pq.poll();
if(visited[current.end]){
continue;
}
visited[current.end]=true;
for(int i=1; i<N+1; i++){
int nextWeight = adj[current.end][i];
if(nextWeight == 0){
continue;
}
if(!visited[i] && minCost[i]> current.weight + nextWeight){
minCost[i] = current.weight + nextWeight;
pq.offer(new Node(i, minCost[i]));
}
}
}
return minCost;
}
private void init(int departure){
minCost = new int[N+1];
Arrays.fill(minCost, Integer.MAX_VALUE);
minCost[departure] = 0;
visited = new boolean[N+1];
}
class Node implements Comparable<Node>{
int end;
int weight;
Node(int end, int weight){
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Node o){
return this.weight - o.weight;
}
}
}
수정한 부분: for내 다익스트라 호출 -> s출발, a출발, b출발했을 때의 minCost배열 구하고 여기서 최솟값 구함
int[] startS = dijkstra(s);
int[] startA = dijkstra(a);
int[] startB = dijkstra(b);
for(int i=1; i<N+1; i++){
res = Math.min(res, startS[i]+startA[i]+startB[i]);
}정점 S에서 출발했을 때 모든 정점과의 최단거리 배열, 정점 A에서 출발했을 때 모든 정점과의 최단거리 배열, 정점 B에서 출발했을 때 모든 정점과의 최단거리 배열을 구하고 각 최단거리 배열의 같은 인덱스의 값을 더해 최소값을 갱신한다.
이 코드 블럭을 처음봤을 땐 직관적으로 이해가 되지 않았다. 그런데 곱씹어보니 이해가 되더라,,
어쨌든 구해야하는건 정점 S와 모든 정점 사이의 최단거리이고 그 정점으로부터 A까지의 최단거리와 B까지의 최단거리를 더한 값이다. 그런데 위처럼 구현해도 이전 코드에서의 결과값과 같은 값이 나온다. 예를 들어 i가 10일 때 S부터 10까지의 최단거리 + A부터 10까지의 최단거리 + B부터 10까지의 최단거리를 구하게 되는데, 이는 dijkstra(s,10)+dijkstra(10,a)+dijkstra(10,b)와 같은 값이다. 어차피 양방향 그래프이므로 출발지, 도착지가 서로 바뀌어도 상관없다.
1부터 n까지 반복문을 돌며 매번 다익스트라를 세번씩 호출한 값을 더하는 것에서 다익스트라를 세번만 호출하고 1부터 n까지 반복문을 돌며 정답을 구하는 것으로 바뀐 것이다. 이게 언뜻 보면 말장난 같은데 시간복잡도를 계산해보자
전자의 경우, \( n*3*ElogE\) 이며, 후자의 경우, \(3*ElogE+n\) 이다. 문제의 조건에 따라 \(n=200, E=19900\)이라고 했을 때, 각각 약 \(48,000,000\), 약 \(240,000\)의 시간복잡도가 발생한다.
머리만 잘굴려도 200배의 성능 향상을 이뤄낼 수 있었다...
한번 베스트 코드 봤으니 비슷한 문제에서는 효율적으로 풀어내보자..^^