[백준]11779번 최소비용구하기2
집안에 큰 일이 있었다. 감정적으로 슬픈 일은 내가 아무리 극복해보려 해도 힘든 것 같다.
그래도 준비가 된다면 다시 잘 시작해봐야지
[백준]11779번 최소비용구하기2
풀이생각
-
양의 간선으로 이루어진 그래프에서, 최소비용을 구하기 위해서는 디익스트라 알고리즘을 보통 사용한다.
-
일반적인 디익스트라 알고리즘에서는 "경로"를 출력할 수는 없었다.
-
경로를 출력하려면 어떻게 해야할까?
- 디익스트라 알고리즘은, 최소비용테이블에서, 아직 방문한적 없으면서, 현재 최소경로를 가진 node를 탐색해서 , 해당 노드를 거쳐 해당노드의 인접노드들로 가는 거리를 업데이트 하는 알고리즘이다.
- 이 때, 이런식으로 탐색하여 pick하게 되는 node는, 해당 노드까지의 최소 경로가 정해지게 되는 것이다.
-
각 노드에 대한 경로를 저장하는 테이블또한 생성한다 : List[] path
- 이 테이블은 현재까지 , 해당 노드까지의 최소 경로가 update 될 때 마다 update한다
- path[intermeidateNode] + 해당노드
- 이 테이블은 현재까지 , 해당 노드까지의 최소 경로가 update 될 때 마다 update한다
잘못생각했던것 : 문제를 제대로 읽자
- 양방향이라 생각하고 풀고 있었다...
틀렸다
- 일단, 이 틀린 풀이에서는, 어떤 노드의 최소 경로를 업데이트 할 때 마다, 모든 경로를 각 노드의 StringBuilder 에 업데이트 시켰다.
package coding;
import java.io.*;
import java.util.*;
public class Main {
public static BufferedReaderbr= new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriterbw= new BufferedWriter(new OutputStreamWriter(System.out));
public static StringTokenizerst;
public static intn,m,s,d;// s: 시작점, d: 도착점
// 그래프 정보
public static List<int[]>[]graph= new List[1001];
// 최소비용 테이블
public static int[]distance= new int[1001];
// path 정보 테이블
// public static List<Integer>[] paths = new List[1001];
public static StringBuilder[]paths= new StringBuilder[1001];
public static void setting() throws IOException {
n= Integer.parseInt(br.readLine());
m= Integer.parseInt(br.readLine());
// 비용 테이블 초기화
Arrays.fill(distance,Integer.MAX_VALUE);
// 비용 그래프 초기화
for(int i=1;i<=n;i++){
graph[i]= new ArrayList<>();
paths[i]= new StringBuilder("");
}
// 간선 정보 받기
int v1=0,v2=0,w=0;
for(int i=0;i<m;i++){
st= new StringTokenizer(br.readLine());
v1 = Integer.parseInt(st.nextToken());
v2 = Integer.parseInt(st.nextToken());
w = Integer.parseInt(st.nextToken());
graph[v1].add(new int[]{v2,w});
}
st= new StringTokenizer(br.readLine());
s= Integer.parseInt(st.nextToken());
d= Integer.parseInt(st.nextToken());
distance[s]=0;
}
public static void dikstra() throws IOException {
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
@Override
public int compare(int[] o1,int[] o2){
return o1[1]-o2[1];
}
});
pq.add(new int[]{s,0});
//경로 업데이트
paths[s].append(s);
int[] cur =null,next=null;
int cv=0,clen=0,nv=0,nlen=0;
while(pq.isEmpty()==false){
// 현재 최소 경로를 pick
cur = pq.poll();
clen=cur[1];
cv=cur[0];
// System.out.println("CURRENT : "+cv);
// 중복되어 pq에 들어오는 것들이 있기 때문에 distance보다 크거나 같으면 pass한다
// System.out.println(cv+"'s distance : "+distance[cv]);
// System.out.println("clen : "+clen);
if(distance[cv]<clen) continue;
for(int i=0;i<graph[cv].size();i++){
next=graph[cv].get(i);
nlen =clen + next[1];
// clen + next[1]이 distance[next[0]]보다 작으면 업데이트(distance,path) &&pq에 넣는다
if(nlen >=distance[next[0]])continue;
// System.out.println("NEXT : "+next[0]+", nlen :"+nlen);
pq.add(new int[]{next[0],nlen});
distance[next[0]]=nlen;
paths[next[0]].delete(0,paths[next[0]].length());
paths[next[0]].append(paths[cv]); // cur까지의 경로
paths[next[0]].append(next[0]); // 경로에 자기자신을 추가
}
}
int i=0;
// 자기자신에서 자기자신으로 가는 경우
if(s==d){
bw.write(distance[d]+"\n");
bw.write(paths[d].length()+"\n");
bw.write(s+" "+d);
}
else {
bw.write(distance[d] + "\n");
bw.write(paths[d].length() + "\n");
for (i = 0; i <paths[d].length()-1; i++) {
bw.write(paths[d].charAt(i) + " ");
}
bw.write(paths[d].charAt(i));
}
bw.flush();
bw.close();
br.close();
}
public static void main(String[] args)throws IOException {
setting();
dikstra();
}
}
다른 사람들의 풀이를 보았다
내가 위에서 하고자 했던 것은, 각 node마다, 해당 노드까지의 [ 모든 경로 ] 를 저장 해 두는 것이었다. ( 차라리 시간초과가 나면 모를까 , 아예 틀린 것은 아직 이해가 되지 않는다 )
이것 말고, 각 노드에서
- 여기서 각 노드란, 거리 테이블에서 , 현재 가장 최소비용을 가진 노드를 말한다.
- 이 노드가 이 비용을 갖기 위해서는, picked되었던 어떤 노드의 인접 노드였기 때문이다.
- 따라서, 이 노드의 이전 노드 ( picked되었던 노드 ) 정보, 그리고 , 이제까지 방문한 노드의 수를 저장하여 traceBack될 수 있도록 한다.
❓중간 과정에서, 현재 picked된 노드가, dest 인지 확인 하는 코드를 넣는 것이 좋을까? → no
- 각 노드의 이전 노드를 저장하는 table을 생성한다 =⇒ pre table . 이 테이블은, 이 노드의 현재 최소 비용을 업데이트 시켜줬던 노드에 해당된다.
package coding;
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public class Main{
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static StringTokenizer st;
public static int n,m,s,d;// s: 시작점, d: 도착점
// 이전 노드 저장 테이블
public static int[] pre = new int[1001];
// 루트 저장 스택
public static Deque<Integer> stack = new LinkedList<>();
// 그래프 정보
public static List<int[]>[] graph = new List[1001];
// 최소비용 테이블
public static int[] distance = new int[1001];
public static void setting() throws IOException {
n = Integer.parseInt(br.readLine());
m = Integer.parseInt(br.readLine());
// 비용 테이블 초기화
Arrays.fill(distance,Integer.MAX_VALUE);
Arrays.fill(pre, Integer.MAX_VALUE);
// 비용 그래프 초기화
for(int i=1;i<=n;i++){
graph[i]= new ArrayList<>();
}
// 간선 정보 받기
int v1=0,v2=0,w=0;
for(int i=0;i<m;i++){
st = new StringTokenizer(br.readLine());
v1 = Integer.parseInt(st.nextToken());
v2 = Integer.parseInt(st.nextToken());
w = Integer.parseInt(st.nextToken());
graph[v1].add(new int[]{v2,w});
}
st = new StringTokenizer(br.readLine());
s = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
// 초기화
distance[s]=0;
pre[s]=0; // pre가 0인 노드 ==> 시작점 인 것
}
public static void dikstra() throws IOException {
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
@Override
public int compare(int[] o1,int[] o2){
return o1[1]-o2[1];
}
});
int cv=0,clen=0;
int[] cur = null,next=null;
List<Integer> adj = null;
pq.add(new int[]{s,0});
while(pq.isEmpty()==false){
cur = pq.poll();
clen = cur[1]; cv = cur[0];
// 중복 제거
if(distance[cv]<clen)continue;
int len =graph[cv].size();
// 인접 노드를 iterate
for(int i=0;i<len;i++){
next = graph[cv].get(i);
if(next[1]+clen>=distance[next[0]])continue;
// pq에 넣고, distance update
pq.add(new int[]{next[0],next[1]+clen});
distance[next[0]] = next[1]+clen;
pre[next[0]] = cv;
}
}
}
// pre table에서 d 부터 시작하여 traceback 한다.
public static int traceBack(){
int cnt = 0;
int curv = d;
while(true){
cnt++;
stack.add(curv);
if(pre[curv]==0)break;
// curv 를 이전 노드로 update한다.
curv = pre[curv];
}
return cnt;
}
public static void main(String[] args)throws IOException {
setting();
dikstra();
int cnt = traceBack();
// 최소 비용 출력
System.out.println(distance[d]);
// 경로 노드 개수 출력
System.out.println(cnt);
// stack에 들어있는 것을 출력한다 : Deque에서 forEach가 돌아가는 순서는 어떻게 될 까 ? -> Queue
while(stack.isEmpty()==false){
System.out.print(stack.pollLast() + " ");
}
br.close();
}
}
Author And Source
이 문제에 관하여([백준]11779번 최소비용구하기2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ynoolee/백준11779번-최소비용구하기2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)