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

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

 

문제 분석

• N개의 도시와, M개의 간선으로 이루어져 있음. 각 도시는 0 ~ N-1번까지 번호가 붙어져 있으며, 각 간선은 방향성을 가지지 않음.
• 각 도시를 연결하는 간선은 여러 개가 존재할 수 있으며, 또한 자신을 향하는 간선 또한 존재할 수 있음.
• 초기 출발지는 무조건 0번 도시로 고정되어 있음.
• 랜드마크 건설
  • 도시의 수 n 과 간선의 수 m, 그리고 m 개의 간선에 해당하는 정보 (u, v, w)가 주어짐.
  • (u, v, w)는 u와 v 도시가 w 가중치로 연결되어 있다는 것을 의미함.
• 여행 상품 생성
  • 여행사는 (pid, revenue, destination) 정보를 가지고 있는 여행 상품을 만들고, 관리 목록에 추가함.
  • destination에 가면 revenue를 얻는다는 의미와 동일함.
  • 최대 3만번 명령으로 주어짐
• 여행 상품 취소
  • pid에 해당하는 여행 상품이 존재한다면, 해당 여행 상품을 삭제함.
  • 최대 3만번 명령으로 주어짐
• 최적의 여행 상품 판매
  • 조건에 맞는 최적의 여행 상품을 선택하여 판매함.
  • 선택 조건은 여행사가 상품을 판매함으로써 얻는 이득 (revenue - min_cost)가 최대인 상품을 우선적으로 고려하며, 이러한 상품이 많을 경우 pid가 낮은 여행 상품을 판매함.
  • 출발지에서 dest를 가는 것이 불가능하거나, min_cost가 revenue보다 큰 경우에는 여행사가 수익을 얻을 수 없기 때문에 -1을 출력하고 상품을 판매하지 않음.
  • 최대 3만번 명령으로 주어짐.
• 여행 상품 출발지 변경
  • 기존 K였던 출발지를 S로 변경하는 행위. 
  • 최대 15번 명령으로 주어짐.
• 총 명령은 최대 10만번 주어지며, 명령에 맞게 작동하여 알맞은 답을 출력하는 프로그램을 작성하는 문제.

 

문제 접근

• 초기 생각
  • 여행 상품을 생성하고 취소하는 행위가 최대 6만번 수행되기 떄문에, O(1)로 수행하는 것이 핵심이라고 판단하였으며, 이에 해싱이 가능한 딕셔너리 자료구조를 활용하여 관리.
  • 시간초과를 줄여야 하는 곳은 곳은 "최적의 여행 상품 판매" 명령이며, 사전에 구해둔 시작 지점으로부터 모든 노드로의 최단 거리를 바탕으로 상품을 탐색. 
  • 매 턴 다익스트라를 구하게 되면 당연히 시간 초과가 날 것이기 때문에, 시작 지점이 갱신되는 5번째 명령어가 호출될 때마다 갱신하도록 로직 구현.=> 시간 초과가 발생했으며, "최적 여행 상품 판매" 명령을 최적화하지 못한 것이라 생각함.=> 결국에는 3만번 수행되는 여행 상품 추가에 의하여, 최대 3만개의 여행 상품을 3만번 수행하면 9억번의 연산으로 인해 시간 초과가 나타난다는 것을 알게 됨.
• 시간 초과 후
  
  • "최적 여행 상품" 판매 명령을 O(N)이 아닌, O(1)이나 O(log N)으로 줄여야 한다고 생각이 듦.
  • 즉, 추가할 때 O(1) / 상품 탐색 시 O(N)을, 추가할 때 O(log N) / 상품 탐색 시 O(log N)으로 줄이면 평균 시간복잡도가 많이 감소하게 되고, 이를 위해 최적의 상품임을 판단하기 위한 우선순위 큐를 생성하여 관리.
  • 발생할 수 있는 문제는 아무래도 특정 상품을 제거할 때 전체탐색 + 삭제 과정이 이뤄져야 한다는 것이다. 하지만, 이를 매 번 명령 시마다 수행하는 것이 아닌, 최적의 여행 상품을 pop할 때 처리해줌으로써 삭제 O(1) / 최적 여행 상품 pop KO(log N)으로 수행할 수 있음.=> 시간 초과를 피할 수 있었음.

 

소스 코드

# define lib
import heapq
from collections import defaultdict

# set value from input
N, M, SID, SID_DIST = -1, -1, 0, None
graph, edge_set = defaultdict(lambda: 1e9), defaultdict(set)
iid_to_rev, iid_to_dest = dict(), dict()
item_queue, item_pop = [], set()

# define function
def initialize(line):
    global N, M, SID
    N, M, edges = line[0], line[1], line[2:]
    for i in range(0, len(edges)//3):
        u, v, w = edges[i*3:(i+1)*3]
        if graph[(u, v)] > w:
            graph[(u, v)] = w
            graph[(v, u)] = w
        edge_set[u].add(v)
        edge_set[v].add(u)
    find_min_dist(SID)

def create_item(line):
    global SID_DIST, item_queue
    iid, irev, idest = line
    iid_to_dest[iid] = idest
    iid_to_rev[iid] = irev
    if irev - SID_DIST[idest] >= 0:
        heapq.heappush(item_queue, (-(irev - SID_DIST[idest]), iid))

def remove_item(iid):
    if iid_to_dest.get(iid, -1) != -1:
        del iid_to_dest[iid]
        del iid_to_rev[iid]
        item_pop.add(iid)

def sell_optimal_item():
    global item_queue
    while item_queue:
        rev, iid = heapq.heappop(item_queue)
        if iid in item_pop:
            continue
        del iid_to_dest[iid]
        del iid_to_rev[iid]
        return iid
    return -1

def change_spt(NSID):
    global SID
    SID = NSID
    find_min_dist(SID)

def find_min_dist(SID):
    global SID_DIST
    dist = [int(1e9)]*N
    hq, dist[SID] = [(0, SID)], 0

    while hq:
        ccost, cid = heapq.heappop(hq)
        if dist[cid] < ccost:
            continue
        for npt in edge_set[cid]:
            if dist[npt] > ccost + graph[(cid, npt)]:
                dist[npt] = ccost + graph[(cid, npt)]
                heapq.heappush(hq, (ccost + graph[(cid, npt)], npt))
    SID_DIST = dist

def update_item_queue():
    global SID, SID_DIST, item_queue, item_pop
    pids = [pid for pid in range(N) if SID_DIST[pid] < int(1e8)]
    iids = [k for k, v in iid_to_dest.items() if v in pids]
    
    _candits = []
    for iid in iids:
        if iid in item_pop:
            continue
        iid_rev, iid_dest = iid_to_rev[iid], iid_to_dest[iid]
        if iid_rev - SID_DIST[iid_dest] >= 0:
            heapq.heappush(_candits, (-(iid_rev - SID_DIST[iid_dest]), iid))
    item_queue = _candits
    item_pop.clear()

for _ in range(int(input())):
    cmd, *line = list(map(int, input().split()))
    if cmd == 100:
        initialize(line)
        update_item_queue()
    elif cmd == 200:
        create_item(line)
    elif cmd == 300:
        remove_item(line[0])
    elif cmd == 400:
        print(sell_optimal_item())
    elif cmd == 500:
        change_spt(line[0])
        update_item_queue()

• 제출 횟수: 2회
• 풀이 시간: 70분