https://www.acmicpc.net/problem/11779
11779번: 최소비용 구하기 2
첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스
www.acmicpc.net
📌 - 처음 생각한 풀이
- 도시와의 거리 = 시작지점을 제외하고는 전부 int 최댓값 초기화 , 이전도시 정보 배열 초기화
- 인접리스트를 이용해서 리스트에 인접한 도시와 비용을 객체로 추가
- bfs로 도시들을 방문
- 비용이 최소일 때만 업데이트
- 업데이트 할 때 그 비용은 dp배열에 저장하고 해당도시를 방문하기 전 도시를 result배열에 저장 - result 배열을 역순으로 출력
처음 푼 코드는 답이 정확하게 나왔지만 메모리초과가 계속 발생해서 애를 먹었는데, 알고보니 bfs로 탐색을 할 때,
백준에 있는 값으로 예시를 들면 1번 도시에서 2,3,4,5번에 전부 접근이 가능하기 때문에 큐에 2,3,4,5도시의 경로와 비용이 함께 들어가게된다. | (2,2),(3,3),(4,1),(5,10) |
해당 4번 도시를 방문해서 4번 도시의 인접 도시를 찾아서 계산할때 이미 5번 도시는 최소 경로인 4로 변경이 되지만 아직 큐에 (5,10)이 남아있는데 이 경우를 연산에 포함하지 않게 해야 메모리나 시간초과를 넘길 수 있다.
해당 코드를 구현하지 않으면 문제를 틀리게 된다.
🔥 - Java 코드
package 그래프탐색.G3_11779_최소비용구하기2;
import java.io.*;
import java.util.*;
class Line{
int x;
int cost;
Line(int x , int cost){
this.x=x;
this.cost=cost;
}
}
public class Main {
public static int n,m;
public static List<ArrayList<Line>> line;
public static int[] dp,result;
public static void main(String[] args) throws IOException {
//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(br.readLine());
line = new ArrayList<>();
dp = new int[n+1];
result = new int[n+1];
for (int i =0;i<n+1;i++){
line.add(new ArrayList<Line>());
}
// 그래프에 인접도시 객체 추가
for(int i=0;i<m;i++){
st = new StringTokenizer(br.readLine());
int a,b,cost;
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
cost = Integer.parseInt(st.nextToken());
line.get(a).add(new Line(b,cost));
}
st = new StringTokenizer(br.readLine());
int sC = Integer.parseInt(st.nextToken());
int sA = Integer.parseInt(st.nextToken());
// 거리 값 전부 최댓값으로 초기화
Arrays.fill(dp, Integer.MAX_VALUE);
dp[sC] = 0;
bfs(sC); // 다익스트라 시작
int count =0;
System.out.println(dp[sA]);
while(dp[sA] != 0){
count++;
sb.insert(0,sA + " ");
sA = result[sA];
}
sb.insert(0,sC+ " ");
System.out.println(count+1);
System.out.println(sb);
}
public static void bfs(int start){
Queue<Line> q = new LinkedList<>();
q.add(new Line(start,0));
while(!q.isEmpty()){
Line x = q.poll();
int cur = x.x;
if(dp[cur] < x.cost){ // ******** 위쪽에서 예시를 든 핵심 코드가 이것이다. 이 코드가 없으면 메모리나 시간초과가 나온다.
continue;
} // ***********
for(int i =0;i<line.get(cur).size();i++){
int nx =line.get(cur).get(i).x;
int nc = line.get(cur).get(i).cost;
if(dp[nx] > nc+dp[cur]){ //
dp[nx] = nc+dp[cur];
result[nx] = cur;
q.add(new Line(nx,dp[nx]));
}
}
}
}
}