[코드트리][기출문제] 코드트리 투어

자료구조를 제외한 라이브러리 최대한 사용하지 않고 문제풀기 (필요하면 직접 코딩)

문제

코드트리 채점기

자료구조 및 알고리즘

• dictionary, set, heap

문제 풀이 및 회고

코드(python)

메모리 초과 코드

from collections import deque

def setting(info: list): # 100 n m v_1 u_1 w_1 v_2 u_2 w_2 ... v_m u_m w_m
    """
    n개의 도시, m개의 간선 (u, v, w)
    """
    global codetree_land
    n, m = info[1], info[2]

    codetree_land = [[] for _ in range(n)]

    for i in range(m):
        v, u, w = info[3+3*i], info[4+3*i], info[5+3*i]
        codetree_land[v].append([u, w])
        codetree_land[u].append([v, w])
    return None

def generate_item(command: list): # 200 id revenue dest
    """
    (id, revenue, dest)에 해당하는 여행 상품을 추가로 만들고, 관리 목록에 추가.
    고유한 식별자 id를 가지며, 해당 상품을 통해 여행사가 얻게 되는 매출은 revenue, 도착지는 dest. 주어지는 id는 모두 다름.
    최대 30,000번
    """
    global items, start_point, codetree_land
    id_, revenue, dest = command[1], command[2], command[3]

    get_min_cost(id_, revenue, dest)
    return None

def get_min_cost(id_, revenue, dest):
    """
    id_ revenue, dest에 해당하는 min_cost를 갱신 / 추가 하기
    """
    global codetree_land, start_point, items

    # start -> dest 까지 cost 계산.
    visited = set()
    visited.add(start_point)
    q = deque()
    q.append([start_point, 0, visited]) # 시작위치, cost, 방문 유무
    min_cost = float("inf")

    while q:
        now_point, now_cost, now_visited = q.popleft()
        if now_point == dest: # 도착한 경우
            min_cost = min(min_cost, now_cost)

        for next_info in codetree_land[now_point]: # 연결된 것들 탐색
            next_point, next_cost = next_info
            if next_point not in now_visited: # 방문 안한 경우
                next_visited = now_visited.copy()
                next_visited.add(next_point)
                q.append([next_point, now_cost + next_cost, next_visited])
    
    items[id_] = [dest, revenue, min_cost] # 관리목록에 갱신
    return None


def cancel_item(command: list): # 300 id
    """
    고유 식별자 id에 해당하는 여행 상품이 존재하는 경우, id의 여행 상품을 관리 목록에서 삭제해야함.
    최대 30,000번
    """
    global items

    items.pop(command[1], None)
    return None

def optimal_sell_item(): # 400
    """
    상품을 판매함으로써 얻게 되는 이득 revenue - cost 최대. 같은 값을 가지는 상품이 여러개 있을 경우, id가 가장 작은 상품을 선택
    만약 dest로 도달할 수 없거나 cost가 revenue보다 크면 판매 불가 상품. 판매 가능한 상품 중에 우선 순위가 높은 상품을 고르기
    최적 여행 상품 id 출력. 이를 관리 목록에서 제외. 만족하는 상품 없으면 -1
    최대 30,000번. 
    """
    global items

    if len(items) == 0: # 상품이 더이상 없음
        print(-1)
        return None
    
    now_info = sorted(items.items(), key=lambda x:(x[1][1]-x[1][2], -x[0]), reverse=True)

    if now_info[0][1][1] < now_info[0][1][2]: # 이득을 볼 수 없는 상황. cost가 revenue보다 크거나 도달할 수 없는 경우
        print(-1)
        return None

    print(now_info[0][0]) # 판매 가능한 상품 중에 우선 순위가 가장 높은 상품
    items.pop(now_info[0][0], None) # 이후에 관리 목록에서 제외
    return None

def change_start_point(command: list): # 500 s
    """
    여행 상품 출발지를 전부 s로 변경
    최대 15번
    """
    global items, start_point

    new_start_point = command[1]
    
    if new_start_point == start_point: # 동일한 시작점이면 굳이 바꿔줄 필요 없음
        return None

    start_point = new_start_point # 새로운 start_point로 변경
    all_items = items.items()

    for item in all_items: # items[id_] = [dest, revenue, min_cost]
        id_, item_info = item
        get_min_cost(id_, item_info[1], item_info[0]) # (id_, revenue, dest)
    return None

start_point = 0
items = {} # [id] = [dest, revenue, cost]
codetree_land = []

if __name__ == "__main__":
    Q = int(input())
    setting(list(map(int, input().split())))

    stop = -1
    for q in range(2, Q+1):
        command = list(map(int, input().split()))
        if command[0] == 200:
            generate_item(command)
        elif command[0] == 300:
            cancel_item(command)
        elif command[0] == 400:
            optimal_sell_item()
        elif command[0] == 500:
            change_start_point(command)

        if q == stop:
            print("now command : ", command)
            print("now items : ", items)
            break

시간초과 2 ㄷ ㄷ …

from collections import deque

def setting(info: list): # 100 n m v_1 u_1 w_1 v_2 u_2 w_2 ... v_m u_m w_m
    """
    n개의 도시, m개의 간선 (u, v, w)
    """
    global codetree_land, codetree_cost_map
    n, m = info[1], info[2]

    codetree_land = [[] for _ in range(n)]

    for i in range(m):
        v, u, w = info[3+3*i], info[4+3*i], info[5+3*i]
        codetree_land[v].append([u, w])
        codetree_land[u].append([v, w])

    codetree_cost_map = [[float("inf")]*n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            get_min_cost_(i, j)
    return None

def get_min_cost_(u, v):
    global codetree_land, codetree_cost_map
    if codetree_cost_map[v][u] != float("inf"): # 만약 v->u로 가는게 이미 계산되어 있다면 굳이 계산할 필요 없음
        codetree_cost_map[u][v] = codetree_cost_map[v][u]
    if u == v: # 시작과 도착점 같으면 cost = 0
        codetree_cost_map[u][v], codetree_cost_map[v][u] = 0, 0
    
    visited = set()
    visited.add(u)
    q = deque()
    q.append([u, 0, visited])
    while q:
        now_point, now_cost, now_visited = q.popleft()
        codetree_cost_map[u][now_point] = min(codetree_cost_map[u][now_point], now_cost)

        for next_info in codetree_land[now_point]: # 연결된 것들 탐색
            next_point, next_cost = next_info
            if next_point not in now_visited: # 방문 안한 경우
                next_visited = now_visited.copy()
                next_visited.add(next_point)
                q.append([next_point, now_cost + next_cost, next_visited])
    return None

def show_cost_map():
    global codetree_cost_map
    for i in range(len(codetree_cost_map)):
        print(codetree_cost_map[i])
    
    return None

def generate_item(command: list): # 200 id revenue dest
    """
    (id, revenue, dest)에 해당하는 여행 상품을 추가로 만들고, 관리 목록에 추가.
    고유한 식별자 id를 가지며, 해당 상품을 통해 여행사가 얻게 되는 매출은 revenue, 도착지는 dest. 주어지는 id는 모두 다름.
    최대 30,000번
    """
    global items, start_point, codetree_cost_map
    id_, revenue, dest = command[1], command[2], command[3]

    items[id_] = [dest, revenue, codetree_cost_map[start_point][dest]]
    return None

def cancel_item(command: list): # 300 id
    """
    고유 식별자 id에 해당하는 여행 상품이 존재하는 경우, id의 여행 상품을 관리 목록에서 삭제해야함.
    최대 30,000번
    """
    global items

    items.pop(command[1], None)
    return None

def optimal_sell_item(): # 400
    """
    상품을 판매함으로써 얻게 되는 이득 revenue - cost 최대. 같은 값을 가지는 상품이 여러개 있을 경우, id가 가장 작은 상품을 선택
    만약 dest로 도달할 수 없거나 cost가 revenue보다 크면 판매 불가 상품. 판매 가능한 상품 중에 우선 순위가 높은 상품을 고르기
    최적 여행 상품 id 출력. 이를 관리 목록에서 제외. 만족하는 상품 없으면 -1
    최대 30,000번. 
    """
    global items

    if len(items) == 0: # 상품이 더이상 없음
        print(-1)
        return None
    
    now_info = sorted(items.items(), key=lambda x:(x[1][1]-x[1][2], -x[0]), reverse=True)

    if now_info[0][1][1] < now_info[0][1][2]: # 이득을 볼 수 없는 상황. cost가 revenue보다 크거나 도달할 수 없는 경우
        print(-1)
        return None

    print(now_info[0][0]) # 판매 가능한 상품 중에 우선 순위가 가장 높은 상품
    items.pop(now_info[0][0], None) # 이후에 관리 목록에서 제외
    return None

def change_start_point(command: list): # 500 s
    """
    여행 상품 출발지를 전부 s로 변경
    최대 15번
    """
    global items, start_point, codetree_cost_map

    new_start_point = command[1]
    
    if new_start_point == start_point: # 동일한 시작점이면 굳이 바꿔줄 필요 없음
        return None

    start_point = new_start_point # 새로운 start_point로 변경
    all_items = items.items()

    for item in all_items: # items[id_] = [dest, revenue, min_cost]
        id_, item_info = item
        items[id_] = [item_info[0], item_info[1], codetree_cost_map[start_point][item_info[0]]]
    return None

start_point = 0
items = {} # [id] = [dest, revenue, cost]
codetree_land = []
codetree_cost_map = []

if __name__ == "__main__":
    Q = int(input())
    setting(list(map(int, input().split())))
    #print("cost map : ")
    #show_cost_map()

    stop = -1
    for q in range(2, Q+1):
        command = list(map(int, input().split()))
        if command[0] == 200:
            generate_item(command)
        elif command[0] == 300:
            cancel_item(command)
        elif command[0] == 400:
            optimal_sell_item()
        elif command[0] == 500:
            change_start_point(command)

        if q == stop:
            print("now command : ", command)
            print("now items : ", items)
            break