[프로그래머스] 2021 KAKAO BLIND RECRUITMENT - "합승 택시 요금" (Java) (dijkstra, floydWarshall)

https://programmers.co.kr/learn/courses/30/lessons/72413

코딩테스트 연습 - 합승 택시 요금

합승 택시 요금

---

 

난이도 : Level 3

 

 그래프에서 최단 경로 알고리즘인 플로이드 - 와샬과 다익스트라 알고리즘으로 해결할 수 있는 문제입니다. 이 알고리즘을 아느냐 모르느냐가 이 문제를 해결할 수 있는 조건이라고 볼 수 있습니다. 일반적인 구현에서 벗어난 실질적인 알고리즘을 사용해야 하는 문제라고 생각합니다.  

 

 두 알고리즘 각각 코드를 보여드리겠습니다. 

 

 

1. Dijkstra ( 다익스트라 )

 

- static final int INF = 99999999;

infinity의 약자인 무한대를 뜻하는 INF 상수입니다. 상수라고 해서 무작정 Integer.MAX_VALUE 코드를 넣으면 오버플로우가 발생할 수 있으므로, 적절한 값을 잘 설정해서 넣어야합니다. 아래 링크에 이유를 설명했습니다.

https://bbangson.tistory.com/74?category=924985 

[Java] 다익스트라(Dijkstra) 알고리즘.

 

 

- static ArrayList<Edge> graph[ ]

 일반 배열이 아닌 ArrayList 자료구조를 사용하여 그래프를 구현하였습니다. 다음 정점과 그 정점까지의 가중치를 저장하는 Edge Class를 별도로 구현하였으며, ArrayList의 타입으로 선언하였습니다. 

 

 

 

- int solution(int n, int s, int a, int b, int[][] fares)

 지점의 개수 n, 출발 지점을 나타내는 s, A 사람의 도착지점을 나타내는 a, B 사람의 도착지점을 나타내는 b, 지점 사이의 예상 택시요금을 나타내는 fares 배열을 파라미터로 받습니다. graph 변수를 초기화 해주며, 방향성이 없는 그래프이므로 fares 배열을 바탕으로 graph의 값을 양방향으로 채워줍니다. 

 

 fromStart는 s지점에서 시작한 모든 지점으로부터의 최단 거리를 저장하는 배열입니다. 마찬가지로  fromA는 A지점에서 시작, fromB는 B지점에서 시작한 모든 지점으로부터의 최단 거리를 저장하는 배열입니다. 이들을 dijkstra 메소드를 통하여 각각 최단 거리를 업데이트 해줍니다. 그 다음 모든 지점을 탐색하여 각 지점으로부터의 거리의 합이 최소가 되는 값을 answer 배열에 저장합니다. 

 

 

 

- int[] dijkstra(int s, int dist[])

 다익스트라 알고리즘을 구현한 함수입니다. 다익스트라의 자세한 설명은 위 링크를 참고해주시면 감사하겠습니다.

 

  코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class PM_72413{
	// PM / 72413번 / 합승 택시 요금 / 다익스트라  / Level3 / 2021 KAKAO BLIND
	static final int INF = 99999999;
	static ArrayList<Edge> graph[];
	
    public int solution(int n, int s, int a, int b, int[][] fares) {
	int answer = INF;
		
	graph = new ArrayList[n+1];
		
	for(int i=0; i<graph.length; i++) {
		graph[i] = new ArrayList<>();
	}
		
	for(int i=0; i<fares.length; i++) {
		graph[fares[i][0]].add(new Edge(fares[i][1], fares[i][2]));
		graph[fares[i][1]].add(new Edge(fares[i][0], fares[i][2]));
	}
	int fromStart[] = new int[n+1];
	int fromA[] = new int[n+1];
	int fromB[] = new int[n+1];
		
	fromStart = dijkstra(s, fromStart);
	fromA = dijkstra(a, fromA);
	fromB = dijkstra(b, fromB);
		
	for(int i=1; i<=n; i++) {
		answer = Math.min(answer, fromStart[i] + fromA[i] + fromB[i]);
	}
	return answer; 
    }
    
    public int[] dijkstra(int s, int dist[]) {
    	PriorityQueue<Edge> pq = new PriorityQueue<>( new Comparator<Edge>() {
			@Override
			public int compare(Edge o1, Edge o2) {
				return o1.w - o2.w;
			}
    	});
    	Arrays.fill(dist, INF);
    	dist[s] = 0;
    	
    	pq.add(new Edge(s, 0));
    	
    	while(!pq.isEmpty()) {
    		Edge now = pq.poll();
    		
    		if(now.w > dist[now.v]) continue;
    		
    		for(int i=0; i<graph[now.v].size(); i++) {
    			Edge next = graph[now.v].get(i);
    			
    			if(dist[next.v] > dist[now.v] + next.w) {
    				dist[next.v] = dist[now.v] + next.w;
    				pq.add(new Edge(next.v, dist[next.v]));
    			}
    		}
    	} 
    	return dist;
    }
}

class Edge{
	int v,w;
	public Edge(int v,int w) {
		this.v = v;
		this.w = w;
	}
}

 

 

 

 

2. Floyd-Warshall ( 플로이드 - 와샬 )

 

- static final int INF = 9999999;

infinity의 약자인 무한대를 뜻하는 INF 상수입니다. 

 

 

 

- static int [][] dist;

플로이드-와샬 알고리즘을 이용하여 각 지점 사이의 최단 거리를 저장할 배열입니다.

 

 

 

- int solution(int n, int s, int a, int b, int[][] fares)

 dist 배열을 초기화 해주며, fares 파라미터 배열을 바탕으로 dist 배열을 채워줍니다. (양방향) 

FloydWarshall() 함수를 호출하여 dist 배열을 업데이트 합니다. 그 후, 모든 경유지를 탐색하며 시작점으로부터 경유지, 경유지부터 A지점, 경유지부터 B지점의 거리를 모두 더한 최소 값을 answer에 저장합니다. 

 

 

 

- void FloydWarshall(int n)

 플로이드 - 와샬 알고리즘을 구현한 함수입니다. 이 알고리즘에 대한 자세한 설명은 생략하겠습니다. 

 

 

  코드

public class PM_72413 {
	// PM / 72413번 / 합승 택시 요금 / 플로이드 와샬  / Level3 / 2021 KAKAO BLIND
	static final int INF = 9999999;
	static int [][] dist;
	public static int solution(int n, int s, int a, int b, int[][] fares) {
		int answer = INF;
		
		dist = new int[n+1][n+1];
		
		for(int i=0; i<dist.length; i++) {
			for(int j=0; j<dist.length; j++) {
				if(i == j) dist[i][j] = 0;
				else dist[i][j] = INF;
			}
		}
		
		for(int i=0; i<fares.length; i++) {
			dist[fares[i][0]][fares[i][1]] = fares[i][2];
			dist[fares[i][1]][fares[i][0]] = fares[i][2];
		}
		
		FloydWarshall(n);
		
		for(int k=0; k<=n; k++) {
			answer = Math.min(answer, dist[s][k] + dist[k][a] + dist[k][b]);
		}
		return answer; 
	}
	
	public static void FloydWarshall(int n) {
		
		for(int k=0; k<dist.length; k++) {
			for(int i=0; i<dist.length; i++) {
				for(int j=0; j<dist.length; j++) {
					if(dist[i][j] > dist[i][k] + dist[k][j]) {
						dist[i][j] = dist[i][k] + dist[k][j];
					}
				}
			}
		}
	}
}

 

피드백 환영합니다.