250615

250615 회고 💬

닌텐도 스위치 2를 구매했다. 젤다의 전설을 다시 플레이하는 중인데 새롭다. 화질, 프레임만 좀 향상 됐을 뿐인데 완전 다른 게임같다. 재밌다. 또 겜송세월 보낼까봐 걱정이다. 😋

Keep 👍

알고리즘

다익스트라 문제를 계속해서 풀고 있다. 백준에 있는 다익스트라 골드 문제는 다 풀어버리겠다는 무식한 도전 진행 중이다. 그리고 SSAFY 시작 반년만에 골드 1을 다시 달성했다. 약 반년만에 도달했다. 무식하게 계속 하니까 실력이 오르긴 한듯,,, ㅎ

• 최소비용 구하기 2 : 다익스트라 + 경로추적 문제다. 이전에 경로추적 문제를 접해봤다면 쉽게 풀 수 있다.

출퇴근 자투리 공부

SSAFY 방학으로 출퇴근 시간 공부는 안 했다.

Try 🧚

• msa 공부하기
• 개인 프로젝트 진행하기
  - 백엔드
  - 테스트 코드 고도화(레스트 독스)
  - Video 도메인 테스트
  - 레스트 독스 구현
  - 비디오 썸네일 작업
  - ResponseBodyAdvice 적용하기
• 최소 1곳 이상 회사 지원하기
  - 이력서
  - 포트폴리오
• 매일 골드 이상 난의도의 알고리즘 문제 풀이 진행하기
• 책 읽기

독서 목록

서평 완료 목록

• 혼자 공부하는 컴퓨터 구조 + 운영체제
• 프로그래머의 길, 멘토에게 묻다
• 함께 자라기 애자일로 가는 길
• 객체지향의 사실과 오해

서평 예정 목록 (읽는 중)

• 면접을 위한 CS 전공지식 노트
• 한 권으로 읽는 컴퓨터 구조와 프로그래밍

독서 예정 목록

• 오브젝트
• HTTP 완벽 가이드
• 자바/스프링 개발자를 위한 실용주의 프로그래밍
• 모던 자바 인 액션
• 자바 성능 튜닝 이야기
• 헤드 퍼스트 서블릿
• 파이브 라인스 오브 코드

Extras

최소비용 구하기 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    
    public static void main(String[] args) {
        new Main().run();
    }

    private void run() {
        Input ip = readInput();
        System.out.println(new Solution().solution(ip.numOfNodes, ip.edges, ip.startNode, ip.targetNode));
    }

    private Input readInput() {
        try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            int numOfNodes = Integer.parseInt(br.readLine());
            int numOfEdges = Integer.parseInt(br.readLine());

            int[][] edges = new int[numOfEdges][3];

            for(int i = 0; i < numOfEdges; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                edges[i][0] = Integer.parseInt(st.nextToken());
                edges[i][1] = Integer.parseInt(st.nextToken());
                edges[i][2] = Integer.parseInt(st.nextToken());
            }

            StringTokenizer st = new StringTokenizer(br.readLine());
            int startNode = Integer.parseInt(st.nextToken());
            int targetNode = Integer.parseInt(st.nextToken());

            return new Input(numOfNodes, edges, startNode, targetNode);

        }catch(IOException e) {
            throw new RuntimeException();
        }
    }

    private static class Input {

        final int numOfNodes;
        final int[][] edges;
        final int startNode;
        final int targetNode;

        public Input(int numOfNodes, int[][] edges, int startNode, int targetNode) {
            this.numOfNodes = numOfNodes;
            this.edges = edges;
            this.startNode = startNode;
            this.targetNode = targetNode;
        }
    }
}

class Solution {

    private static final int INF = Integer.MAX_VALUE;

    private List<List<int[]>> graph;
    private int[] dist;
    private int[] prev;

    public String solution(int numOfNodes, int[][] edges, int startNode, int targetNode) {
        init(numOfNodes, edges);
        calc(startNode);
        return getAnswer(targetNode);
    }

    private void init(int numOfNodes, int[][] edges) {
        this.graph = new ArrayList<>();
        this.dist = new int[numOfNodes + 1];
        this.prev = new int[numOfNodes + 1];

        for(int i = 0; i <= numOfNodes; i++) graph.add(new ArrayList<>());

        for(int[] edge : edges) {
            graph.get(edge[0]).add(new int[] {edge[1], edge[2]});
        }

        Arrays.fill(dist, INF);
    }

    private void calc(int startNode) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        pq.offer(new int[] {startNode, 0});
        dist[startNode] = 0;
        prev[startNode] = -1;

        while(!pq.isEmpty()) {
            int[] cur = pq.poll();

            if(dist[cur[0]] < cur[1]) continue;

            for(int[] node : graph.get(cur[0])) {
                int next = node[0];
                int weight = node[1];
                int nextWeight = dist[cur[0]] + weight;

                if(dist[next] <= nextWeight) continue;

                pq.offer(new int[] {next, nextWeight});
                dist[next] = nextWeight;
                prev[next] = cur[0];
            }
        }
    }

    private String getAnswer(int targetNode) {
        StringBuilder answer = new StringBuilder();
        answer.append(dist[targetNode]).append("\n");
        
        List<Integer> steps = new ArrayList<>();

        int cnt = 0;
        int step = targetNode;

        while(step != -1) {
            cnt++;
            steps.add(step);
            step = prev[step];
        }

        answer.append(cnt).append("\n");

        while(!steps.isEmpty()) {
            answer.append(steps.get(steps.size() - 1)).append(" ");
            steps.remove(steps.size() - 1);
        }

        return answer.toString();
    }
}