[백준] G5. 택배 배송 (Java)

문제

농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.

농부 현서에게는 지도가 있습니다. N (1 <= N <= 50,000) 개의 헛간과, 소들의 길인 M (1 <= M <= 50,000) 개의 양방향 길이 그려져 있고, 각각의 길은 C_i (0 <= C_i <= 1,000) 마리의 소가 있습니다. 소들의 길은 두 개의 떨어진 헛간인 A_i 와 B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i)를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.

다음 지도를 참고하세요.

           [2]---
          / |    \\
         /1 |     \\ 6
        /   |      \\
     [1]   0|    --[3]
        \\   |   /     \\2
        4\\  |  /4      [6]
          \\ | /       /1
           [4]-----[5]
                3

농부 현서가 선택할 수 있는 최선의 통로는 1 -> 2 -> 4 -> 5 -> 6 입니다. 왜냐하면 여물의 총합이 1 + 0 + 3 + 1 = 5 이기 때문입니다.

농부 현서의 지도가 주어지고, 지나가는 길에 소를 만나면 줘야할 여물의 비용이 주어질 때 최소 여물은 얼마일까요? 농부 현서는 가는 길의 길이는 고려하지 않습니다.

입력

첫째 줄에 N과 M이 공백을 사이에 두고 주어집니다.

둘째 줄부터 M+1번째 줄까지 세 개의 정수 A_i, B_i, C_i가 주어집니다.

출력

첫째 줄에 농부 현서가 가져가야 될 최소 여물을 출력합니다.

---

사전 지식

다익스트라 알고리즘

가중치 있는 그래프에서, 한 노드에서 다른 노드까지의 ‘최소 비용 경로’를 구한다.

• 간선에 음수 가중치가 없음
• 최단 거리만 필요

수행 과정

1. 출발 노드와 도착 노드 설정
2. 최단 거리 테이블 초기화
3. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드들 중 거리가 가장 짧은(가중치가 가장 작은) 노드를 선택하여 방문 처리 (우선순위큐 사용)
4. 해당 노드 거쳐 다른 노드 가능 비용 계산하여 비용이 작으면 최단 거리 테이블 갱신
5. 2, 3번 과정 반복

벨만-포드 알고리즘

매 단계마다 모든 간선을 확인하면서 모든 노드 간의 최단 거리를 구하므로 음수 간선이 있어도 최적의 해를 찾을 수 있다.

• 간선에 음수 가중치가 있어도 가능
• 음의 사이클이 없는 그래프에서 적용

수행 과정

1. 출발 노드 설정
2. 최단 거리 테이블 초기화
3. 다음 과정 (정점 개수 - 1)번 반복
   1. 모든 간선 E개를 하나씩 확인
   2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
4. 음수 간선 순환이 발생하는지 체크하고 싶으면 3번 더 수행 → 최단 거리 테이블이 갱신되면 음수 사이클이 존재

우선순위큐

원시타입 배열 기준 정렬

Comparator.comparingInt(a -> a[1])

Comparator.comparingLong(a -> a[1])

Comparator.comparingDouble(a -> a[1])

객체타입 배열 기준 정렬

Comparator.comparing(a -> a[1])

풀이

접근 방법

1. LRU 알고리즘 활용한 기본 클래스 만들기
2. 필요없는 로직 제외 ex. map의 value, get 메소드
3. 실행시간을 측정하는 메소드 만들기
4. 해당 클래스에 capacity 0인 예외를 고려하는 로직 집어 넣기

풀이 코드

import java.util.*;

class Solution {
    class Node {
        String key;
        Node prev, next;

        public Node(String key) {
            this.key = key;
        }
    }

    public class LRUCache {
        private HashMap<String, Node> map;
        private Node head, tail;
        private int capacity;
        private int time;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.map = new HashMap<>();
            time = 0;
            this.head = null;
            this.tail = null;
        }
        // 노드 삭제
        private void remove(Node node) {
            if (node.prev != null) {
                node.prev.next = node.next;
            } else {
                head = node.next;
            }
            if (node.next != null) {
                node.next.prev = node.prev;
            } else {
                tail = node.prev;
            }
        }
				// 사용한 노드 헤드로 보내기
        private void moveToHead(Node node) {
            if (head == null) {
                head = tail = node;
                node.prev = node.next = null;
            } else {
                node.next = head;
                node.prev = null;
                head.prev = node;
                head = node;
            }
        }
				// 캐시에 집어넣기
        public void put(String key) {
            Node node;
            // 해당 메모리가 캐시에 있는 경우 (히트)
            if (map.containsKey(key)) {
                node = map.get(key);
                remove(node);
                time += 1;
            // 해당 메모리가 캐시에 없는 경우 (미스)
            } else {
                if (map.size() == capacity) {
                    // 꼬리가 있는 경우만 제거 (용량이 0인 경우 고려)
                    if (tail != null) {
                        map.remove(tail.key);
                        remove(tail);
                    }
                }
                node = new Node(key);
                time += 5;
            }
            // 용량이 0이 아니면 집어넣기
            if (capacity != 0) {
                moveToHead(node);
                map.put(key, node);
            }
        }
				// 시간을 구하는 메소드
        public int getTime() {
            return time;
        }
    }
    
    public int solution(int cacheSize, String[] cities) {
        LRUCache cache = new LRUCache(cacheSize);

        for (String city : cities) {
            cache.put(city.toLowerCase());  // 대소문자 통일
        }

        return cache.getTime();
    }
}

느낀점

LRU 알고리즘을 처음 구해봐서 거의 블로그의 도움을 구했다.

나중에 다시 한번 내 스스로 구현 해봐야겠다.