[Java] 백준 1916.최소 비용구하기

➡️문제 링크

https://www.acmicpc.net/problem/1916

 

 

💡아이디어

다익스트라

 

처음에는 단순 bfs로 que에 넣다빼서 값을 비교해야하나 싶었는데

-> 각 도시로 이동하는 비용이 다름

-> 가중치가 다른 그래프

-> 다익스트라

싶었다

 

 

✏️문제 풀이

1. 다익스트라 시도 - 오답

비용이 작은 것을 기준으로 정렬해 pq를 써야 한다는 것은 알았는데 

계속 메모리 초과가 났다.

visited 배열을 쓰는게 맞나 싶기도 하고 값도 비교하는데 왜 안되는지 이해가 안가

이번에는 제미나이한테 물어봤다

import java.io.*;
import java.util.*;

public class Main{
	static int N, M;
	static List<List<int []>> graph = new ArrayList<>();
	public static void main(String [] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		for(int i = 0; i <= N; i++) {
			graph.add(new ArrayList<>());
		}
		
		for(int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			
			graph.get(s).add(new int[] {e, cost});
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		
		// 구현 및 출력
		System.out.println(bfs(start, end));
		
	}
	
	static int bfs(int start, int end) {
		PriorityQueue<int []> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);	// 비용 기준 올림차순 정렬
		
		int [] arr = new int[N+1];
		Arrays.fill(arr, Integer.MAX_VALUE);
		arr[start] = 0;

		pq.add(new int [] {start, 0});	// 현재 위치, 누적 비용
		int minCost = Integer.MAX_VALUE;
		
		while(!pq.isEmpty()) {
			int [] point = pq.poll();
			if(point[1] > arr[point[0]]) continue;	// 구하지 않아도 이미 비용이 기존값보다 큼
			
			if(point[0] == end) {
				minCost = point[1];
				break;
			}
			
			List<int []> list = graph.get(point[0]);
			
			for(int i = 0; i < list.size(); i++) {
				int [] curPoint = list.get(i);
				
				if(curPoint[1]+point[1] > arr[curPoint[0]]) continue;
				
				arr[curPoint[0]] = curPoint[1]+point[1];
				pq.add(new int [] {curPoint[0], arr[curPoint[0]]});			
			}
		}
		
		return minCost;
		
	}
}

 

 

2. 다익스트라  - 성공

거의 다 왔는데 "비교"가 잘못되었다고 했다

다익스트라로 접근했을 때, 현재까지의 비용보다 "작은 값"일 경우만 진행해야 하는데,

나는 if(curPoint[1]+point[1] > arr[curPoint[0]]) continue; 같은 경우를 포함시켜버렸다

import java.io.*;
import java.util.*;

public class Main{
	static int N, M;
	static List<List<int []>> graph = new ArrayList<>();
	public static void main(String [] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		for(int i = 0; i <= N; i++) {
			graph.add(new ArrayList<>());
		}
		
		for(int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			
			graph.get(s).add(new int[] {e, cost});
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		
		// 구현 및 출력
		System.out.println(bfs(start, end));
		
	}
	
	static int bfs(int start, int end) {
		PriorityQueue<int []> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);	// 비용 기준 올림차순 정렬
		
		int [] arr = new int[N+1];
		Arrays.fill(arr, Integer.MAX_VALUE);
		arr[start] = 0;

		pq.add(new int [] {start, 0});	// 현재 위치, 누적 비용
		int minCost = Integer.MAX_VALUE;
		
		while(!pq.isEmpty()) {
			int [] point = pq.poll();
			if(point[1] > arr[point[0]]) continue;	// 구하지 않아도 이미 비용이 기존값보다 큼
			
			if(point[0] == end) {
				minCost = point[1];
				break;
			}
			
			List<int []> list = graph.get(point[0]);
			
			for(int i = 0; i < list.size(); i++) {
				int [] curPoint = list.get(i);
				
				if(curPoint[1]+point[1] >= arr[curPoint[0]]) continue;
				
				arr[curPoint[0]] = curPoint[1]+point[1];
				pq.add(new int [] {curPoint[0], arr[curPoint[0]]});			
			}
		}
		
		return minCost;
		
	}
}