[ 백준 ] 1446. 지름길

https://www.acmicpc.net/problem/1446

1446번: 지름길

 

그래프 이외의 리스트를 활용하여 다익스트라를 사용하는 방법은 처음이라 여러 시도를 하였다.

더블 정렬처럼 각 노드들에 대해서 수식화 하여 구하였지만, 시작 노드와 끝 노드가 겹치는 상황에서 긴 구간의 가중치가 여러개의 작은 구간들이 가중치의 합보다 클 경우에 대해서(즉, 긴 것 1개 vs 작은 것 2개) 대응을 하지 못하였다.

따라서 각 distance가 담긴 배열을 어떻게 사용할 것인지가 중요한 문제이다. 아래의 코드는 graph의 가중치로 지름길이 생긴 상황인 distance[i]와 지름길이 아닌 길로 갔을 때의 값을 이전 값 + 1를 서로 비교한 것이다.

distance[i] = min(distance[i], distance[i-1]+1)

 

이를 이용한 완성된 코드는 다음과 같다.

import sys
input = sys.stdin.readline

N, goal = map(int, input().split())
graph = [[] for _ in range(10001)]

for _ in range(N):
    s, e, w = map(int, input().split())
    graph[s].append([e, w])

distance = [i for i in range(goal+1)]

for i in range(goal+1):
    if  i != 0:
        distance[i] = min(distance[i], distance[i-1]+1)

    for e, w in graph[i]:
        if e <= goal and distance[e] > w + distance[i]:
            distance[e] = w + distance[i]

print(distance[goal])

 

디버깅을 위한 코드 분석한 자료이다.

 

실패 코드도 작성하였다.

N, goal = map(int, input().split())
row_data = [list(map(int, input().split()))for _ in range(N)]
distance = set()

graph = []
for x, y, z in row_data:
    if y <= goal:
        graph.append([x, y, z])
graph = sorted(graph)

for i in range(len(graph)):
    As, Ae, Aw = graph[i][0], graph[i][1], graph[i][2]
    check = True
    if Ae - As < Aw:
        continue

    for j in range(i + 1, len(graph)):
        Bs, Be, Bw = graph[j][0], graph[j][1], graph[j][2]
        if As == Bs and Ae == Be and Aw == Bw:
            continue
        if (As <= Bs <= Ae) or (As <= Be <= Ae) or (Bs <= As <= Be) or (Bs <= As <= Be):
            start_node = min(As, Bs)
            end_node = min(Ae, Be)

            diff = end_node - start_node
            case1 = diff - (Ae - As) + Aw
            case2 = diff - (Be - Bs) + Bw

            if case1 < case2:
                distance.add((As, Ae, Aw))
                check = False
                continue
            elif case1 > case2:
                distance.add((Bs, Be, Bw))
                check = False
                continue
    if check:
        distance.add((As, Ae, Aw))

# 정답 처리

print(distance)
for s_node, e_node, weight in distance:
    goal -= (e_node - s_node)
    goal += weight
    
print(goal)