[코드트리][Python] 삼성 SW 역량테스트 2024 상반기 오전 2번 문제 - 코드트리 투어

📚 문제

https://www.codetree.ai/training-field/frequent-problems/problems/codetree-tour/description?page=1&pageSize=5

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

---

💡 풀이 과정

• 다익스트라 알고리즘을 사용해 기본 출발지로부터 거리를 계산한다.
• 이후 상품을 생성하면서 value 를 기준으로 최소 힙에 저장한다.
• 상품 삭제 시에는 heap 에서 바로 삭제하기보다는 deleted Set 으로 관리하였다. 
• 출발지 변경 시 다익스트라 알고리즘을 다시 사용하고 기존 상품들의 Value 값을 재계산한다.
  • 재계산을 위해 상품에는 수익과 목적지가 모두 기록되어야한다. 

---

📌 포인트

• 삭제 시 deleted Set 에 바로 추가하는 것이 아니라 현재 해당 상품이 있다면 추가해야한다.
  • 따라서 products_id Set 을 따로 관리해줬다.
• 최적 여행 상품 판매 시 판매할 상품이 없으면 pop 하지 않고 -1 만 출력함에 주의한다.
  • 이들은 출발지가 바뀌었을 때 사용될 수 있다. 

---

💻  코드

# https://www.codetree.ai/training-field/frequent-problems/problems/codetree-tour/description?page=1&pageSize=5

"""
- 100 : 코드트리 랜드 건설
    - 간선 및 가중치 정보가 가장 처음 주어진다.
    - 기본 출발지를 기준으로 cost 계산
- 200 : 여행 상품 생성
    - id, revenue, dest 형태
    - cost 까지 계산해서 최소힙에 상품 저장
- 300 : 여행 상품 취소
    - id 값을 기준으로 여행 상품 삭제
- 400 : 최적의 여행 상품 판매
    - 최적의 여행 상품을 출력하며 제외
- 500 : 여행 상품의 출발지 변경
    - cost 재계산 및 여행 상품들 가격 재비교

최적의 여행 상품을 생성하고 뽑아내야하기에 최소합을 사용하는 게 좋아 보인다.
하지만 삭제가 있으니 따로 삭제 Set 을 생성하자.
"""

import sys
import heapq

input = sys.stdin.readline

graph = []
costs = []
n = 0
m = 0
products = []
products_id = set()
deleted = set()  # 삭제된 여행 상품의 ID를 저장하는 set


def make_roads(data):
    global n, m, graph

    n = data[0]
    m = data[1]
    graph = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(2, len(data), 3):
        if graph[data[i]][data[i + 1]] == 0 or graph[data[i]][data[i + 1]] > data[i + 2]:
            graph[data[i]][data[i + 1]] = data[i + 2]
            graph[data[i + 1]][data[i]] = data[i + 2]

    dijkstra(0)


def dijkstra(start_node):
    global costs, graph, n

    costs = [float('inf') for _ in range(n)]
    minHeap = [(0, start_node)]
    costs[start_node] = 0

    while minHeap:
        current_distance, current_node = heapq.heappop(minHeap)

        if current_distance > costs[current_node]:
            continue

        for i in range(n):
            if graph[current_node][i] != 0:
                distance = graph[current_node][i] + current_distance

                if distance < costs[i]:
                    costs[i] = distance
                    heapq.heappush(minHeap, (distance, i))


def add_product(product_id, revenue, dest):
    global costs, products

    cost = costs[dest]
    value = revenue - cost
    heapq.heappush(products, (-value, product_id, revenue, dest))
    products_id.add(product_id)


def cancel_product(product_id):
    if product_id in products_id:
        deleted.add(product_id)
        products_id.remove(product_id)


def sell_best_product():
    global products

    if products:
        while products:
            value, id, revenue, dest = products[0]
            if id in deleted:
                heapq.heappop(products)
                deleted.remove(id)
                continue

            if  value <= 0:  # 삭제되지 않은 상품만 처리
                heapq.heappop(products)
                products_id.remove(id)
                print(id)
                return
            else:
                print(-1)
                return
    print(-1)  # 판매 가능한 상품이 없을 때


def change_departure(new_start):
    dijkstra(new_start)
    # 기존 상품들에 대한 비용을 다시 계산
    new_products = []
    for value, product_id, revenue, dest in products:
        if product_id not in deleted:
            new_cost = costs[dest]
            value = revenue - new_cost
            heapq.heappush(new_products, (-value , product_id, revenue, dest))
    deleted.clear()
    products[:] = new_products


def solv():
    Q = int(input())

    for _ in range(Q):
        commands = list(map(int, input().split()))
        if commands[0] == 100:
            make_roads(commands[1:])
        elif commands[0] == 200:
            product_id, revenue, dest = commands[1], commands[2], commands[3]
            add_product(product_id, revenue, dest)
        elif commands[0] == 300:
            product_id = commands[1]
            cancel_product(product_id)
        elif commands[0] == 400:
            sell_best_product()
        elif commands[0] == 500:
            new_start = commands[1]
            change_departure(new_start)


solv()