글 읽기 - 파이썬 시간초과 질문드립니다. BFS로 풀 수는 없을까요?

pepper_mis 3년 전 0

사이클이 될까봐 특정목적지 까지의 최소시간과 최소시간에 드는 비용을 저장해두고 시간이 더 걸리면서 비용도 더 큰 경우는 제외되도록 만들었습니다.

마지막에 여기에서 N에 해당하는 최소시간을 출력하도록 만들었어요.

12퍼센트가 되자마자 시간초과가 뜨는데, 어떤 경우에 오래걸리는 걸까요?

import sys
from collections import deque
#input = sys.stdin.readline
INF = sys.maxsize

T = int(input())
for t in range(T):
    N, M, K = map(int, input().split()) #공항의 수N, 총 지원비용 M, 티켓정보 수 K
    graph = [[] for i in range(N + 1)]
    for k in range(K):
        u, v, c, d = map(int, input().split()) #출발, 도착, 비용, 시간
        graph[u].append([v, c, d])

    dp = [[INF for i in range(N+1)] for i in range(M+1)]
    queue = deque()
    queue.append([1, 0])
    dp[0][1] = 0
    min_time = [[INF, INF] for i in range(N + 1)] #최소시간과 비용 저장
    while queue:
        start, total_cost = queue.popleft()
        for end, cost, time in graph[start]:
            total_add_cost = total_cost + cost #1부터 다음 목적지까지의 비용
            total_add_time = time + dp[total_cost][start] #1부터 다음 목적지까지의 시간
            if total_add_cost <= M and dp[cost+total_cost][end] > total_add_time and (min_time[end][0] > total_add_time or min_time[end][1] > total_add_cost):
                dp[cost+total_cost][end] = total_add_time
                min_time[end] = min(min_time[end], [total_add_time, total_add_cost])
                queue.append([end, total_add_cost])

    if min_time[N][0] == INF:
        print("Poor KCM")
    else:
        print(min_time[N][0])

BFS의 전제조건은 '모든 간선의 가중치가 동일해야 한다'입니다. 이 문제와 같이 간선의 가중치가 여러 종류가 나올 수 있는 경우 거리가 갱신될 때마다 큐에 원소를 넣으면 중복된 원소가 들어가기 때문에 비효율적이고, 최악의 경우에는 O((비용의 최댓값)*(정점의 개수))의 시간이 걸리게 됩니다. 이 문제는 다익스트라로 풀어야 하고, 그 중에서도 시간이 촉박한 편에 속합니다.

pepper_mis 3년 전 0

제가 다른분 코드 참고해서 아래 코드 사용해서 통과되었는데, 이거랑 시간복잡도가 다른건가요?

for cost in range(M+1):
        for start in range(1, N+1):

djm03178 3년 전 1

코드를 부분만 올리시면 어떤 식으로 구현되어 있는 것인지 알기가 어렵습니다. 제출하신 코드를 확인해보니 방문 순서 자체가 cost의 오름차순이기 때문에 큐를 쓰지 않고도 진행할 수 있고 중복 방문도 일어나지 않습니다. 코드를 다시 보니 지금 코드로도 중복 방문에 대한 처리만 진행하면 같은 시간 복잡도로 통과 가능할 것 같습니다.

pepper_mis 3년 전 0

아하.. 중복 방문처리 차이였나보네요.. 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 시간초과 질문드립니다. BFS로 풀 수는 없을까요?

pepper_mis 3년 전 0

djm03178 3년 전 1

pepper_mis 3년 전 0

djm03178 3년 전 1

pepper_mis 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말