최소비용 구하기 버스문제
문제
문제 아이디어
먼저 문제를 보면 1번 정점에서 N번 정점으로 가는 최소 비용을 구하는 문제이다.
최소 비용 하면 두 가지가 떠오르는데 아무래도 다익스트라 알고리즘을 떠올릴 것이다. 플로이드 워셜은 반드시 거쳐가야할 정점이 있을 때 사용하는 알고리즘이다.
다익스트라 알고리즘은 시작 정점에서 다른 정점으로 가는 최소 비용을 구하는 알고리즘이다.
이 경우에도 같은데 다른 도시 (정점)로 가는 최소 비용을 구하는 것이다.
다익스트라 알고리즘이란 ?
Greedy + DP 알고리즘
- Greedy : 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- DP : 한 번 계산한 결과를 메모리 공간에 메모하는 방법
다익스트라 알고리즘은 그리디 알고리즘으로 분류되지만 DP로 분류되기도 한다. 두 가지 모두를 사용하기 때문이다.
간단한 순서를 보자면
- 출발 노드를 설정한다.
- 최단 거리 테이블을 초기화한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 3, 4번을 반복한다.
알고리즘의 기능 목록을 설정하자면 위와 같다.
그래서 제대로 뭔지 아직 감이 안잡 힐 수 있는데
그리디 알고리즘을 사용한다고 했다.
현재 위치에서 다음 위치로 갈 때 가장 짧은 거리를 선택한다. ( Greedy )
짧은 거리로 선택한 노드로 이동한 뒤 현재 위치에서 다른 노드로 가는 비용을 계산한다. ( DP )
- Start 를 A , 가장 짧은 노드가 B 였다면 B 로 이동 후 B와 연결된 모든 노드들로 이동하는 비용을 계산 후 최소비용을 갱신한다.
이렇게 반복하면 최단거리를 구할 수 있다.
그러면 이제 문제를 풀어보자
문제풀이
문제 TODO
- 1번째 줄 : 도시의 개수 N , 버스의 개수 M
- 2번째 줄 ~ M+1번째 줄 : 버스의 정보 ( 출발 도시 , 도착 도시 , 비용 )
- M+2번째 줄 : 최소 비용을 구해야 하는 출발 도시와 도착 도시
- 출력 : 최소 비용
기능 목록
- Input 받기
- 그래프 생성 및 초기화
- 최단 거리 테이블 초기화
- 다익스트라 알고리즘 수행
- 최소 비용 노드 선택
- 최소 비용 테이블 갱신
- 최소 비용 출력
일단 필요한 기능들을 정리해보았다. 하나씩 차근 차근 구현해보자.
Input 받기 및 그래프 , 최단 거리 테이블 생성 초기화
// 첫째줄 도시 개수
// 둘째 줄 버스의 개수
// 세쨋줄 부터 버스 정보 // 버스 출발 도시 번호 , 도착지 번호 // 버스 비용
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 정점의 개수 1 <= N <= 1000
int M = Integer.parseInt(br.readLine()); // 간선의 개수 1 <= M <= 100,000
ArrayList<ArrayList<Node>> graph = new ArrayList<>();
// 최초 그래프 생성 , 각 정점마다 연결된 간선 정보를 담는 리스트를 생성
for (int i = 0 ; i < N + 1 ; i++){
graph.add(new ArrayList<>());
}
// 간선의 개수 만큼 반복하며 그래프 정보 입력 받기
for (int i = 0; i < M; i++){
int[] ints = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int start = ints[0];
int dest = ints[1];
int cost = ints[2];
// start to dest by cost
graph.get(start).add(new Node(dest , cost));
}
// 문제에서 요구하는 시작점 및 도착지 받기
int[] ints = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int start = ints[0];
int dest = ints[1];
// 방문 여부를 체크할 배열
boolean[] visited = new boolean[N + 1]; // 도시 방문 체킹
int[] dist = new int[N + 1]; // 매번 거리 정보를 갱신할 배열 선언
// 최단 거리 테이블을 무한으로 초기화
for (int i = 0; i < N + 1 ; i++){
// 초기 값을 최대값으로 초기화 , 최소 거리를 구하는 것이기 때문에
dist[i] = Integer.MAX_VALUE;
}다익스트라
public static void dijkstra(boolean[] visited , ArrayList<ArrayList<Node>> graph , int[] dist ){
int N = visited.length; // 정점의 수
// 0번째는 안쓴다 문제에서 1번 부터 주어져서 안헷갈리게
for (int i = 1; i < N; i++){
int nodeValue = Integer.MAX_VALUE;
int nodeIdx = 0;
for (int j = 1 ; j < N; j++){
// 방문하지 않은 노드 중 최소 값의 노드를 찾는다.
// 함수 실행 전 dist[start] 값을 0 으로 했기 떄문에 start 노드에서 먼저 시작된다.
if(!visited[j] && dist[j] < nodeValue) {
nodeValue = dist[j];
nodeIdx = j;
}
}
// 여기서 방문 처리를 해줘야 한다. , 방문 처리를 안해주면 무한루프에 빠진다.
visited[nodeIdx] = true; // 선택된 노드 방문 처리
// 선택 된 노드로 최소 비용 갱신
renew(nodeIdx , graph , dist);
}
}
public static void renew(int nodeIdx , ArrayList<ArrayList<Node>> graph , int[] dist){
for (int j = 0; j < graph.get(nodeIdx).size(); j++){
Node node = graph.get(nodeIdx).get(j);
// 인접 노드로 가는 비용이 저장된 최소 비용보다
// 현재 노드로 가는 최소 비용과 인접 노드로 가는 값과을 더해 비교 하여 작은 값으로 갱신
if(dist[node.index] > dist[nodeIdx] + node.cost){
dist[node.index] = dist[nodeIdx] + node.cost;
}
}
} 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Stream;
class 최소비용구하기 {
public static void main(String[] args) throws IOException {
// 첫째줄 도시 개수
// 둘째 줄 버스의 개수
// 세쨋줄 부터 버스 정보 // 버스 출발 도시 번호 , 도착지 번호 // 버스 비용
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 정점의 개수 1 <= N <= 1000
int M = Integer.parseInt(br.readLine()); // 간선의 개수 1 <= M <= 100,000
ArrayList<ArrayList<Node>> graph = new ArrayList<>();
for (int i = 0 ; i < N + 1 ; i++){
graph.add(new ArrayList<>());
}
for (int i = 0; i < M; i++){
int[] ints = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int start = ints[0];
int dest = ints[1];
int cost = ints[2];
// start to dest by cost
graph.get(start).add(new Node(dest , cost));
}
int[] ints = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int start = ints[0];
int dest = ints[1];
boolean[] visited = new boolean[N + 1]; // 도시 방문 체킹
int[] dist = new int[N + 1]; // 매번 거리 정보를 갱신할 배열 선언
for (int i = 0; i < N + 1 ; i++){
// 초기 값을 최대값으로 초기화 , 최소 거리를 구하는 것이기 때문에
dist[i] = Integer.MAX_VALUE;
}
dist[start] = 0;
dijkstra(visited ,graph , dist);
//System.out.println(Arrays.toString(dist));
System.out.println(dist[dest]);
}
public static void dijkstra(boolean[] visited , ArrayList<ArrayList<Node>> graph , int[] dist ){
int N = visited.length; // 정점의 수
// 0번째는 안씀
for (int i = 1; i < N; i++){
int nodeValue = Integer.MAX_VALUE;
int nodeIdx = 0;
for (int j = 1 ; j < N; j++){
// 방문하지 않은 노드 중 최소 값의 노드를 찾는다.
if(!visited[j] && dist[j] < nodeValue) {
nodeValue = dist[j];
nodeIdx = j;
}
}
visited[nodeIdx] = true; // 선택된 노드 방문 처리
// 선택 된 노드로 최소 비용 갱신
renew(nodeIdx , graph , dist);
}
}
public static void renew(int nodeIdx , ArrayList<ArrayList<Node>> graph , int[] dist){
for (int j = 0; j < graph.get(nodeIdx).size(); j++){
Node node = graph.get(nodeIdx).get(j);
// 인접 노드로 가는 비용이 저장된 최소 비용보다
// 현재 노드로 가는 최소 비용과 인접 노드로 가는 값과을 더해 비교 하여 작은 값으로 갱신
if(dist[node.index] > dist[nodeIdx] + node.cost){
dist[node.index] = dist[nodeIdx] + node.cost;
}
}
}
public static class Node {
int index;
int cost;
public Node(int index, int cost) {
this.index = index;
this.cost = cost;
}
}
}
rocoli에요