프로그래머스 합승 택시 요금 (Java,자바)
이번에 풀어본 문제는
프로그래머스 합승 택시 요금 입니다.
📕 문제 링크
❗️코드
import java.util.*;
class Solution {
public int solution(int n, int s, int a, int b, int[][] fares) {
int answer = 0;
int [][] map = new int[n+1][n+1];
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <=n; ++j)
{
map[i][j] = 19900001;
}
map[i][i] = 0;
}
for(int i = 0; i < fares.length; ++i)
{
map[fares[i][0]][fares[i][1]] = fares[i][2];
map[fares[i][1]][fares[i][0]] = fares[i][2];
}
for(int k = 1; k <= n; ++k)
{
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <=n; ++j)
{
if(map[i][j] > map[i][k] + map[k][j]) map[i][j] = map[i][k] + map[k][j];
}
}
}
answer = Integer.MAX_VALUE;
int tmp = 0;
for(int i = 1; i <= n; ++i)
{
tmp = map[s][i] + map[i][a] + map[i][b];
answer = Math.min(answer,tmp);
}
return answer;
}
}
📝 풀이
import java.util.*;
class Solution {
public int solution(int n, int s, int a, int b, int[][] fares) {
int answer = 0;
int [][] map = new int[n+1][n+1];
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <=n; ++j)
{
map[i][j] = 19900001;
}
map[i][i] = 0;
}
for(int i = 0; i < fares.length; ++i)
{
map[fares[i][0]][fares[i][1]] = fares[i][2];
map[fares[i][1]][fares[i][0]] = fares[i][2];
}
for(int k = 1; k <= n; ++k)
{
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <=n; ++j)
{
if(map[i][j] > map[i][k] + map[k][j]) map[i][j] = map[i][k] + map[k][j];
}
}
}
answer = Integer.MAX_VALUE;
int tmp = 0;
for(int i = 1; i <= n; ++i)
{
tmp = map[s][i] + map[i][a] + map[i][b];
answer = Math.min(answer,tmp);
}
return answer;
}
}
📝 풀이
먼저 각 정점간의 최소 비용을 플로이드와샬 알고리즘을 활용해 구해줍니다.
마지막으로 시작점 -> 경유지 -> a / b로의 거리 를 더한 결과 중 최솟값을 answer에 저장해주면 해결됩니다.
📜 후기
내일 시험이라 기출문제 복습중입니다. 화이팅!
Author And Source
이 문제에 관하여(프로그래머스 합승 택시 요금 (Java,자바)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jh5253/프로그래머스-합승-택시-요금-Java자바저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)