집안에 큰 일이 있었다. 감정적으로 슬픈 일은 내가 아무리 극복해보려 해도 힘든 것 같다.
그래도 준비가 된다면 다시 잘 시작해봐야지

[백준]11779번 최소비용구하기2

11779번: 최소비용 구하기 2

풀이생각

• 양의 간선으로 이루어진 그래프에서, 최소비용을 구하기 위해서는 디익스트라 알고리즘을 보통 사용한다.

• 일반적인 디익스트라 알고리즘에서는 "경로"를 출력할 수는 없었다.

• 경로를 출력하려면 어떻게 해야할까?

  • 디익스트라 알고리즘은, 최소비용테이블에서, 아직 방문한적 없으면서, 현재 최소경로를 가진 node를 탐색해서 , 해당 노드를 거쳐 해당노드의 인접노드들로 가는 거리를 업데이트 하는 알고리즘이다.
  • 이 때, 이런식으로 탐색하여 pick하게 되는 node는, 해당 노드까지의 최소 경로가 정해지게 되는 것이다.

• 각 노드에 대한 경로를 저장하는 테이블또한 생성한다 : List[] path

  • 이 테이블은 현재까지 , 해당 노드까지의 최소 경로가 update 될 때 마다 update한다
    • path[intermeidateNode] + 해당노드

잘못생각했던것 : 문제를 제대로 읽자

• 양방향이라 생각하고 풀고 있었다...

틀렸다

• 일단, 이 틀린 풀이에서는, 어떤 노드의 최소 경로를 업데이트 할 때 마다, 모든 경로를 각 노드의 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();
    }
}