들어가며

삼성 SW 역량 테스트 2024년 상반기 오전 2번 문제입니다. 출발점이 되는 기준 도시가 존재하고, 기준 도시로부터 어떤 도시로 가는 여행 상품이 존재할 때, 여행 상품 수익 - 최단 경로 비용 가 최대가 되는 상품을 찾아 판매해 나가는 문제입니다.

각 명령에 대해 최적화를 하지 않으면 시간 초과가 나는 문제였습니다.

문제설명

코드트리 여행사는 코드트리 랜드에서 다양한 여행 상품을 만들어 관리하는 회사입니다. 코드트리 랜드는 n개의 도시와 각 도시 사이를 연결하는 m개의 간선으로 이루어져 있습니다. 각 도시는 0번부터 n - 1번까지의 번호가 붙여져 있고 각 간선은 방향성을 갖지 않습니다. 또, 두 도시를 연결하는 간선은 여러 개가 존재할 수 있으며, 자기 자신을 향하는 간선도 존재할 수 있습니다. 편의 상 여행 상품의 출발지는 하나로 통일되어 있으며 처음 여행 상품의 출발지는 0번 도시입니다.

다섯 개의 명령에 따라 진행됩니다.

코드트리 랜드 건설 : 도시의 수 n과 간선의 수 m, 그리고 m개의 간선에 대한 정보 vi, ui, wi가 주어집니다. 도시 vi와 도시 ui가 가중치 wi로 연결되어 있다는 의미입니다.

여행 상품 생성 : 새로운 여행 상품을 생성합니다. 여행 상품 식별자 id, 여행 상품을 통한 매출 revenue, 도착지 식별자 dest가 주어집니다.

여행 상품 취소 : 식별자 id에 해당하는 여행 상품이 존재하는 경우, 해당 id의 여행 상품을 관리 목록에서 삭제합니다.

최적의 여행 상품 판매 : revenue - cost 가 최대인 상품을 찾아 판매하며, 같은 값을 가진 상품이 여러 개일 경우 id가 가장 작은 상품을 판매합니다. cost 는 출발지로부터 도착지까지 도달하기 위한 최단거리를 의미합니다. 만약 도착지로 도달할 수 없거나, cost 가 revenue 보다 커서 이득을 얻을 수 없는 경우 -1을 출력하고 상품을 제거하지 않습니다.

여행 상품의 출발지 변경 : 여행 상품의 출발지를 새로운 s 번 도시로 변경합니다. 이 명령에 따라 여행 상품들의 cost 가 변경될 수 있습니다.

※ 1번 명령은 1번, 2,3,4번 명령은 30,000번, 5번 명령은 최대 15번 주어집니다.

해설

1. 코드트리 랜드 건설

한 도시에서 모든 도시로의 최단 경로를 구해야 하므로, 다익스트라 알고리즘을 사용합니다. 이 때, 간선의 개수는 노드의 개수에 비해 희소하므로 인접 리스트로 표현하며, 두 도시를 연결하는 간선이 여러 개 존재할 수 있으나 가중치가 가장 낮은 하나만 알고 있으면 되므로 Map구조를 사용해 최소 가중치만 저장합니다.

private static void buildCodeTreeLand(int n, int m, int[][] edgesInfo) {
        edges = new TreeMap[n];
        minDist = new int[n];

        for (int i = 0; i < n; i++) {
            edges[i] = new TreeMap<>();
        }

        for (int i = 0; i < m; i++) {
            int vi = edgesInfo[i][0];
            int ui = edgesInfo[i][1];
            int wi = edgesInfo[i][2];

            if (vi == ui) continue; // 시작 도시와 끝 도시가 같으면 의미없는 간선이므로 패스

            if (edges[vi].containsKey(ui)) { // 간선이 이미 존재한다면
                if (edges[vi].get(ui) > wi) { // 가중치 wi가 저장된 가중치보다 작다면
                    edges[vi].put(ui, wi); // 새롭게 교체
                    edges[ui].put(vi, wi); // 새롭게 교체
                }
            } else {
                edges[vi].put(ui, wi);
                edges[ui].put(vi, wi);
            }
        }

        dijkstra(0); // 0번 도시를 시작점으로 하는 다익스트라 알고리즘 실행
    }

2. 여행 상품 생성

새로운 상품을 저장할 Item 자료 구조를 새로 생성합니다. 이때, 빠른 계산을 위해 (상품의 가치 - 최단 거리)를 계산한 value 도 함께 저장합니다. 만약 현재 기준 도시에서 도달하지 못하는 도시의 상품이라면 idleItems 리스트에 별도로 저장하고, 도달 가능하다면 우선순위 큐인 optimalItems 에 저장합니다.

Item 자료구조는 value 를 기준으로 내림차순으로 정렬하고, 만약 value 가 같다면 id 가 작은 순서로 정렬합니다.

class Item implements Comparable<Item> {
    int id;
    int revenue;
    int dest;
    int value;
    boolean isOut;

    @Override
    public int compareTo(Item o) {
        if (this.value == o.value) {
            return Integer.compare(this.id, o.id);
        }

        return Integer.compare(o.value, this.value);
    }
}

public class Main {
    static Map<Integer, Item> itemList = new HashMap<>();
    static PriorityQueue<Item> optimalItems = new PriorityQueue<>();
    static List<Item> idleItems = new ArrayList<>();
    static int[] minDist;

    private static void createItem(int id, int revenue, int dest) {
        Item item = new Item(); // 새로운 아이템 생성
        item.id = id;
        item.revenue = revenue;
        item.dest = dest;
        item.value = calcValue(dest, revenue); // 가치 계산

        itemList.put(id, item);

        if (item.value == Integer.MIN_VALUE) { // 도달할 수 없는 도시라면
            idleItems.add(item); // 유휴 리스트에 저장
        } else { // 도달할 수 있다면
            optimalItems.add(item); // 우선순위 큐에 저장
        }
    }

    /**
	    가치 계산 메소드
    */
    private static int calcValue(int dest, int revenue) {
        if (minDist[dest] == Integer.MAX_VALUE) { // 기준 도시에서 도달할 수 없는 도시라면
            return Integer.MIN_VALUE; // 가치는 최솟값
        }

        return revenue - minDist[dest]; // 이득 - 최소 거리
    }
}

3. 여행 상품 취소

여행 상품을 관리 목록에서 삭제하는 경우, 우선순위 큐의 중간 쯤에 여행 상품이 존재한다면 제거하기 어렵기 때문에 Item 자료구조의 isOut 값을 true로 설정해 표시하고, 나중에 lazy하게 제거하도록 합니다.

private static void deleteItem(int id) {
    Item item = itemList.get(id);
    if (item != null) {
        item.isOut = true;
    }
}

4. 최적의 여행 상품 판매

최적의 여행 상품을 판매하기 위해서는 우선순위 큐 optimalItems 를 하나씩 뽑으면서 isOut 이 true인 상품은 제거하고, 뽑은 상품을 처리해 출력합니다.

private static int sellOptimalItem() {
    boolean canFind = false;
    Item item = null;

    while (!optimalItems.isEmpty()) {
        item = optimalItems.peek(); // 가장 위의 상품을 보고

        if (item.isOut) { // 이미 제거된 상품이라면
            optimalItems.poll(); // 관리 목록에서 제거
            continue;
        }

        if (item.value < 0) { // 가치가 0보다 작다면 관리 목록에서 이득을 얻을 수 있는 상품이 없으므로 중지
            break;
        }

        canFind = true; // 위의 조건문을 통과했다면 가치가 0보다 큰 상품을 찾았음
        optimalItems.poll();
        break;
    }

    if (canFind) { // 상품을 찾았다면
        item.isOut = true;
        return item.id; // 상품의 id 리턴
    } else { // 알맞은 상품이 없다면
        return -1; // -1 리턴
    }
}

5. 여행 상품의 출발지 변경

이 명령이 최대 15번 일어나므로 다른 명령에 비해 시행하는 횟수가 적습니다. 따라서 이 명령에서 할 수 있는 모든 것을 해야 시간 초과가 일어나지 않습니다.

새로운 도시로 기준 도시를 변경하면 각 도시의 최소 거리 또한 바뀌게 됩니다. 따라서 새롭게 다익스트라 알고리즘을 시행해 최소 거리를 구하고, 그에 따른 여행 상품 Item의 정보도 함께 바꿔 다른 명령에서는 그저 최적의 상품을 뽑거나 제거할 수 있도록 합니다.

기존 기준 도시에서는 갈 수 없었던 도시의 상품이 새로운 기준 도시에서는 갈 수 있게 바뀌었을 수 있기 때문에 idleItems 리스트를 함께 업데이트해줍니다.

private static void changeDeparture(int newDeparture) {
    departure = newDeparture; // 새로운 기준 도시로 변경
    dijkstra(newDeparture); // 다익스트라 재실행
    PriorityQueue<Item> newOptimalItems = new PriorityQueue<>(); // 새로운 우선순위 큐
    List<Item> newIdleItems = new ArrayList<>(); // 새로운 유휴 상품 리스트

    while (!optimalItems.isEmpty()) { // 기존 우선순위 큐를 빼면서 업데이트
        Item item = optimalItems.poll();
        if (item.isOut) continue;

        item.value = calcValue(item.dest, item.revenue);
        if (item.value == Integer.MIN_VALUE) {
            newIdleItems.add(item);
        } else {
            newOptimalItems.add(item);
        }
    }

    for (Item idleItem : idleItems) { // 기존 유휴 상품 리스트를 돌면서 업데이트
        if (idleItem.isOut) continue;

        idleItem.value = calcValue(idleItem.dest, idleItem.revenue);
        if (idleItem.value == Integer.MIN_VALUE) {
            newIdleItems.add(idleItem);
        } else {
            newOptimalItems.add(idleItem);
        }
    }

    idleItems = newIdleItems;
    optimalItems = newOptimalItems;
}

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Item implements Comparable<Item> {
    int id;
    int revenue;
    int dest;
    int value;
    boolean isOut;

    @Override
    public int compareTo(Item o) {
        if (this.value == o.value) {
            return Integer.compare(this.id, o.id);
        }

        return Integer.compare(o.value, this.value);
    }
}

class Node {
    int id, dist;
    Node(int id, int dist) {
        this.id = id;
        this.dist = dist;
    }
}

public class Main {
    static int departure;
    static TreeMap<Integer, Integer>[] edges;
    static Map<Integer, Item> itemList = new HashMap<>();
    static PriorityQueue<Item> optimalItems = new PriorityQueue<>();
    static List<Item> idleItems = new ArrayList<>();
    static int[] minDist;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int comm = Integer.parseInt(st.nextToken());
            int id;

            switch (comm) {
                case 100:
                    int n = Integer.parseInt(st.nextToken());
                    int m = Integer.parseInt(st.nextToken());
                    int[][] edgesInfo = new int[m][3];

                    for (int j = 0; j < m; j++) {
                        edgesInfo[j][0] = Integer.parseInt(st.nextToken());
                        edgesInfo[j][1] = Integer.parseInt(st.nextToken());
                        edgesInfo[j][2] = Integer.parseInt(st.nextToken());
                    }

                    buildCodeTreeLand(n, m, edgesInfo);
                    break;
                case 200:
                    id = Integer.parseInt(st.nextToken());
                    int revenue = Integer.parseInt(st.nextToken());
                    int dest = Integer.parseInt(st.nextToken());

                    createItem(id, revenue, dest);
                    break;
                case 300:
                    id = Integer.parseInt(st.nextToken());
                    deleteItem(id);
                    break;
                case 400:
                    int result2 = sellOptimalItem();
                    sb.append(result2).append("\n");
                    break;
                case 500:
                    int newDeparture = Integer.parseInt(st.nextToken());
                    changeDeparture(newDeparture);
                    break;
            }
        }

        System.out.println(sb);
    }


    private static void buildCodeTreeLand(int n, int m, int[][] edgesInfo) {
        edges = new TreeMap[n];
        minDist = new int[n];

        for (int i = 0; i < n; i++) {
            edges[i] = new TreeMap<>();
        }

        for (int i = 0; i < m; i++) {
            int vi = edgesInfo[i][0];
            int ui = edgesInfo[i][1];
            int wi = edgesInfo[i][2];

            if (vi == ui) continue;

            if (edges[vi].containsKey(ui)) {
                if (edges[vi].get(ui) > wi) {
                    edges[vi].put(ui, wi);
                    edges[ui].put(vi, wi);
                }
            } else {
                edges[vi].put(ui, wi);
                edges[ui].put(vi, wi);
            }
        }

        dijkstra(0);
    }

    private static void dijkstra(int departure) {
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[departure] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.dist, o2.dist));
        pq.add(new Node(departure, 0));

        while(!pq.isEmpty()) {
            Node nxt = pq.poll();
            int id = nxt.id;
            int dist = nxt.dist;

            if (minDist[id] < dist) continue;

            TreeMap<Integer, Integer> edge = edges[id];

            for (Map.Entry<Integer, Integer> comp : edge.entrySet()) {
                int arrival = comp.getKey();
                int weight = comp.getValue();

                if (minDist[arrival] > minDist[id] + weight) {
                    minDist[arrival] = minDist[id] + weight;
                    pq.add(new Node(arrival, minDist[arrival]));
                }
            }
        }
    }

    private static void createItem(int id, int revenue, int dest) {
        Item item = new Item();
        item.id = id;
        item.revenue = revenue;
        item.dest = dest;
        item.value = calcValue(dest, revenue);

        itemList.put(id, item);

        if (item.value == Integer.MIN_VALUE) {
            idleItems.add(item);
        } else {
            optimalItems.add(item);
        }
    }

    private static int calcValue(int dest, int revenue) {
        if (minDist[dest] == Integer.MAX_VALUE) {
            return Integer.MIN_VALUE;
        }

        return revenue - minDist[dest];
    }

    private static void deleteItem(int id) {
        Item item = itemList.get(id);
        if (item != null) {
            item.isOut = true;
        }
    }

    private static int sellOptimalItem() {
        boolean canFind = false;
        Item item = null;

        while (!optimalItems.isEmpty()) {
            item = optimalItems.peek();

            if (item.isOut) {
                optimalItems.poll();
                continue;
            }

            if (item.value < 0) {
                break;
            }

            canFind = true;
            optimalItems.poll();
            break;
        }

        if (canFind) {
            item.isOut = true;
            return item.id;
        } else {

            return -1;
        }
    }

    private static void changeDeparture(int newDeparture) {
        departure = newDeparture;
        dijkstra(newDeparture);
        PriorityQueue<Item> newOptimalItems = new PriorityQueue<>();
        List<Item> newIdleItems = new ArrayList<>();

        while (!optimalItems.isEmpty()) {
            Item item = optimalItems.poll();
            if (item.isOut) continue;

            item.value = calcValue(item.dest, item.revenue);
            if (item.value == Integer.MIN_VALUE) {
                newIdleItems.add(item);
            } else {
                newOptimalItems.add(item);
            }
        }

        for (Item idleItem : idleItems) {
            if (idleItem.isOut) continue;

            idleItem.value = calcValue(idleItem.dest, idleItem.revenue);
            if (idleItem.value == Integer.MIN_VALUE) {
                newIdleItems.add(idleItem);
            } else {
                newOptimalItems.add(idleItem);
            }
        }

        idleItems = newIdleItems;
        optimalItems = newOptimalItems;
    }
}

Loading comments...

Loading table of contents...

Loading related posts...