백준 20183번 골목 대장 호석 - 효율성 2 (Python) .. 우당탕탕 시행착오들..

1. 문제 조건

- N개의 교차로와 M개의 골목 (교차로 : 노드 / 골목 : 간선)

- 각 간선의 가중치가 그 골목의 요금

- 소지한 돈보다 많은 비용이 나오면 그 경로로는 갈 수 없음

- 수치심은 경로 상에서 가장 많이 낸 돈의 금액, 최소한의 수치심을 얻어야 함

- 수치심을 줄일 수록 많은 돈이 필요하고 수치심이 높을 수록 적은 돈이 필요함

 

- 입력

 

- 범위

1 <= N <= 100,000

1 <= M <= 500,000

1 <= C <= 10^14

1 <= 가중치 <= 10^19

1 <= A,B <= N, A !=B

 

 

2. 아이디어 및 시행착오

시행착오 1.  

다익스트라로 경로를 이동하되, 이동한 경로의 총합으로 최소비용을 계산하는 것이 아니라, max 배열을 두고 max배열을 갱신하면서 다익스트라를 돌리려고 했다. (가지고 있는 돈보다 경로를 지나온 합이 작을 때만 갱신하도록 dist배열도 관리를 하긴 한다.) 특정 노드에 왔을 때, 그 노드까지 온 경로의 최댓값을 배열에 저장해두고, N에 도착했을 때만 수치심의 최솟값으로 갱신하도록 구현했다. 하지만, 이럴 경우 시간초과, 메모리 초과가 난다. 현재 꺼낸 노드의 값과 dist 배열의 대소관계를 비교해 continue를 하여 시간을 잡아보려 했으나, dist와 수치심은 반비례하기 때문에, 무조건 dist가 작으면 그 이후를 갈 필요가 없는 상황이 아니라 부적합했다.

 

시행착오 2. 

다익스트라의 시간복잡도는 ElogE. E는 간선의 개수로 문제에서 최대 간선은 50만개이므로, 다익스트라를 여러번 돌려도 괜찮은 정도였다. 따라서 간선들을 우선순위 큐에 넣고 간선의 가중치가 높은 순대로 꺼내, 그 간선을 포함하는 경로를 찾아 다익스트라를 돌리는 방법을 생각했다. 여기서 문제는, 그 간선을 통해 목적지까지 도달하는 경로에서 수치심이 그 간선의 가중치가 아닐 수 있다는 점이다. 더 큰 간선을 지나는 경우가 고려되어선 안된다. 또, 모든 edge에서 경로의 최솟값을 계산해서 answer를 갱신하면, answer가 그냥 간선의 최솟값을 갱신되는 셈이 되어, edge들 중 어느 선까지만 갱신하고 언제는 갱신하지 않을 지를 처리해야 했다.

이런 부분들을 놓치고 구현해서 많이 헤맸었다. 이 부분을 위해 다이그슽라 내에서 max(수치심)로 봐야할 cost를 넘어서면 그 경로를 고려하지 않도록 하고, answer를 최솟값으로 갱신하도록 처리했다. 

위와 같은 작업들을 통해 주어진 테스트케이스는 맞췄지만 해당 풀이는 시간초과로 정답이 될 수 없었다. 최악의 상황까지 고려했을 때, edge들마다 모두 다익스트라를 돌리게 되어 시간복잡도가 M^2logM이 되어버리기 때문이다. 따라서 다른 방법을 고안해야했다... 

 

위 방법으로 구현한 코드는 아래와 같다. (오답코드..) 

import heapq

def dijkstra(s, e, c):
    if s==e:
        return 0

    pq = [(0, s)]
    dist = [inf] * (N + 1)
    dist[s] = 0

    while pq:
        cur_cost, cur_node = heapq.heappop(pq)

        if dist[cur_node] < cur_cost:
            continue

        for edge in edges[cur_node]:
            next_cost, next_node = edge

            if dist[next_node] > cur_cost + next_cost:
                if next_cost > c:
                    continue
                dist[next_node] = cur_cost+ next_cost
                heapq.heappush(pq, (dist[next_node], next_node))

    return dist[e]

#N:노드개수 / M : 간선개수 / S: 시작지점 / E: 끝지점 / C : 보유한 돈
N, M, S, E, C = map(int, input().split())

edges = [[] for i in range(N+1)]
edge_pq = []
for i in range(M):
    st, ed, cost = map(int, input().split())
    edges[st].append((cost, ed))
    edges[ed].append((cost, st))
    heapq.heappush(edge_pq, (-cost, st, ed))

inf = 500_000*10**9
answer = inf
max_cost = 0
#edge_pq에서 cost순으로 뽑아서 걔를 포함하고서 목적지까지 비용내에 도착할 수 있는지 확인
#max가 갱신되면 그대로 종료. 그 때가 최대니까
while edge_pq:
    cost, st, ed = heapq.heappop(edge_pq)
    cost = -cost
    d = 0
    if st == S and ed == E:
        d = dijkstra(S, E, cost)
    else:
        # S -> st 로 가는 최소비용 다익스트라로 구하기
        d += dijkstra(S, st, cost)
        #st에서 E로 가는 최소비용 다익스트라로 구하기
        d += dijkstra(st, E, cost)

    if d <= C and answer > cost:
        answer = cost
print(answer if answer!=inf else -1)

 

 

시행착오 3.

위에서 시간복잡도의 문제를 알아차린 후, 문제 조건에 굵게 표시된 조건이 이제서야 눈에 들어왔다. 수치심과 총 비용이 서로 음의 관계를 가지는 조건이라면 경로를 탐색해서 나온 수치심, 총 비용을 보고 더 큰 간선을 볼지, 더 작은 간선을 볼 지 판단할 수 있겠다는 생각이 들었다. 그리고 시간복잡도를 낮추기 좋은 대표적인 방법 중 하나가 이진탐색이기도 하니까.. 그렇게 해서 이진탐색으로 구현하다가 left, right 조정 조건 헷갈려서 많이 고초를 겪었다. 

left와 right를 조정하기 위한 조건이 다익스트라를 통해 나온 max 값의 수치심과 현재 보고 있는 간선의 가중치와의 대소관계일지, 아니면 총비용이 가진 돈에 미치는지 못 미치는지인지 정리가 안됐었다. 결론은? 총비용으로 이진탐색의 조건을 처리했다. 그리고 현재 수치심으로 고려하고 있는 값보다 큰 간선을 지나는 경우는, 다익스트라 내에서 나보다 큰 간선이 가는 경로는 선택하지 않는 방식을 취함으로써 두 조건의 복잡함을 해결했다.  

 

시행착오 4.

특정 간선이 수치심일 것으로 고려하고 최소비용을 구하는 다익스트라를 실행시키는데, 나는 처음에 dijkstra(출발노드, 간선시작노드)와 dijkstra(간선시작노드, 최종 목표 노드) 를 각각 따로 구해 이 둘의 합을 최소비용으로 생각하여 계산했었다. 그런데 그 간선을 포함하는 최소비용 루트가 꼭 출발 ~ 간선시작 ~ 간선시작~ 최종목표라는 보장이 없다는 것을 간과했다. 이 부분을 그냥 다익스트라를 출발노드부터 돌리는 것으로 바꾸고 대신, 현재 고려 중인 간선보다 더 큰 가중치를 갖는 간선을 지나는 경로는 택하지 않는 방식을 적용하여 해결했다.

 

시행착오 5.

시행착오4까지 오고 나서, 도무지 정답처리가 되지 않는 이유를 알 수 없었다. 로직 상 더이상 틀린 곳이 없어보이는데 말이다. 알고보니 배열의 sort와 heapq를 활용한 heappush는 배열에 저장된 순서가 다를 수 있었다는 점이 원인이었다. 시행착오 2에서 사용한 우선순위큐가 sort와 같은 상태일 거라 생각하고 배열을 그대로 사용한 탓이었다. 이 부분을 배열.sort()로 바꾸니 바로 정답처리가 됐다...

 

 

여기까지 눈물의 호석이 문제 시행착오였다. 

이제 정답코드 보자.

 

 

3. 구현

import heapq
def dijkstra(s, e, c):
    pq = [(0, s, 0)]
    dist = [inf] * (N + 1)
    dist[s] = 0
    m_cost = 0
    while pq:
        cur_cost, cur_node, cur_max = heapq.heappop(pq)

        if dist[cur_node] < cur_cost:
            continue
        for edge in edges[cur_node]:
            next_cost, next_node = edge
            if dist[next_node] > cur_cost + next_cost:
                if next_cost > c:
                    continue
                dist[next_node] = cur_cost+ next_cost
                heapq.heappush(pq, (dist[next_node], next_node, max(next_cost, cur_max)))
    return dist[e]

#N:노드개수 / M : 간선개수 / S: 시작지점 / E: 끝지점 / C : 보유한 돈
N, M, S, E, C = map(int, input().split())

edges = [[] for i in range(N+1)]
edge_pq = []
for i in range(M):
    st, ed, cost = map(int, input().split())
    edges[st].append((cost, ed))
    edges[ed].append((cost, st))
    edge_pq.append((cost, st, ed))
edge_pq.sort()

inf = 500_000*10**9
answer = inf
max_cost = 0

left = 0
right = M-1
while left <= right:
    mid = (left+right)//2

    cost, st, ed = edge_pq[mid]
    # print(cost, st, ed)
    # m_cost = -1
    d = dijkstra(S, E, cost)

    # 나보다 더 큰놈을 지나왔어 ! 그럼 더 큰놈을 지나칠 수밖에 없는 간선이었다는 뜻
    # C보다 더 돈이 많이 드는 길이다! 전체 비용을 줄이려면 수치심을 더 받는 것을 감수해야한다
    # 더 큰 놈 찾으러 가기
    if d>C:
        left = mid+1
    #내가 제일 큰 간선이었다면?
    #더 작은 수치심을 느낄 수 있는 길을 찾아봐야한다...!
    else:
        right = mid-1
        answer = min(cost, answer)

print(answer if answer!=inf else -1)