[파이썬] 백준 5719 : 거의 최단 경로 (플레5)

[파이썬] 백준 5719 : 거의 최단 경로 (플레5)

5719번: 거의 최단 경로

---

문제

---

풀이

0. 방향성 생각

• 다익스트라를 돌려서 end node에 최소 비용으로 도달하는 경우를 찾고, 이 노드들이 어디서 오는지 체크한다.
• 체크를 위해서 trace 변수를 넣어서 각 node로 들어오는 node가 어떤 노드인지 기록한다.
• trace를 이용해서 node를 최단 경로 노드들을 모두 shortcut에 넣는다.
• 다익스트라를 한 번 더 돌려서 end node에 도달할 수 있는지 확인한다.

• 위 방식으로 접근하니까 75%에서 막혔음. (질문 게시판에 있는 83% 테케 참고)
• end node로 가는 cost는 5이고, 최단 경로는 3가지가 있음.
• 빨간 경로는 문제가 안되는데, 주황 경로랑 초록 경로가 2번 노드를 공통으로 지나친다.
• 기존의 코드대로면 end노드만 특별 취급해서 end에서 여러개의 trace를 탐색해서 start로 가는 경로를 모두 제거하는 문제였다.
• end node만 여러개의 리스트로 받을 게 아니라, 어떤 노드에 같은 cost로 들어오면 trace에 노드를 계속 추가해준다.
• 결론적으로 말하면, list에 int형으로 저장했던 코드를 list형으로 바꿨다.
• 기존 trace 추적에서는 while문으로 해도 됐다면, 바꾼 코드에서는 조금 더 복잡해져서 재귀로 DFS를 구현해서 shortcut에 최단 경로 edge들을 추가했다.

1. 다익스트라

def di(a,b):

    visit = [inf]*n    
    visit[a] = 0
    trace = [[] for _ in range(n)]
    heap = [(0,a)]
    while heap:
        c,x = hq.heappop(heap)
        for nx in graph[x]:
            if (x,nx) not in shortcut:
                nc = c + edges[x][nx]      

                if nc < visit[nx]:
                    visit[nx] = nc
                    trace[nx] = [x]
                    if nx != end:
                        hq.heappush(heap,(nc,nx))
                elif nc == visit[nx]:
                    trace[nx].append(x)

    return visit,trace

• trace를 2차원 array로 만들어줘서 trace[x] = [px1,px2 ...] x로 들어오는 prev x를 모두 저장한다. (최소 코스트로 들어오는 경우에만)

2. DFS

def dfs(x):
    global T,shortcut,start,D

    if D[x] or x == start:
        return

    D[x] = True
    for px in T[x]:
        shortcut.add((px,x))
        dfs(px)

• T는 다익스트라에서 얻은 2차원 trace, shortcut은 set으로 저장한 최단경로들.
• D는 재귀에서 재방문 했을 때, 방문체크를 하는 배열
• start,end는 전역변수로 시작할 때 받았던 node
• 재귀를 통해서 shortcut을 모두 찾아준다.

3. 입력/출력

while True:

    n,m = map(int,input().split())

    if (n,m) == (0,0):
        break

    start,end = map(int,input().split())
    graph = [[] for _ in range(n)]
    edges = [[inf]*n for _ in range(n)]
    shortcut = set()

    for _ in range(m):
        x,nx,cost = map(int,input().split())
        graph[x].append(nx)
        edges[x][nx] = cost

    V,T = di(start,end)
    if not V[end]:
        print(-1)
    else:
        D = [False]*n
        dfs(end)
        V,T = di(start,end)
        if V[end] == inf:
            print(-1)
        else:
            print(V[end])

• graph와 edges 정보를 모두 받아준 후, 다익스트라를 돌린다.
• 다익스트라를 돌린 후, end node에 도달하지 못하면 바로 -1
• end node에 도달한 경우, dfs를 돌려서 shortcut을 모두 제거한다.
• 이후 다시 다익스트라를 돌려서 도달할 수 있으면 최소 비용 V[end]를, 그렇지 못하면 -1을 출력한다.

 

---

전체코드

import heapq as hq
import sys
input = lambda : sys.stdin.readline().rstrip()

inf = 1e9

def di(a,b):

    visit = [inf]*n    
    visit[a] = 0
    trace = [[] for _ in range(n)]
    heap = [(0,a)]
    while heap:
        c,x = hq.heappop(heap)
        for nx in graph[x]:
            if (x,nx) not in shortcut:
                nc = c + edges[x][nx]      

                if nc < visit[nx]:
                    visit[nx] = nc
                    trace[nx] = [x]
                    if nx != end:
                        hq.heappush(heap,(nc,nx))
                elif nc == visit[nx]:
                    trace[nx].append(x)

    return visit,trace

def dfs(x):
    global T,shortcut,start,D

    if D[x] or x == start:
        return

    D[x] = True
    for px in T[x]:
        shortcut.add((px,x))
        dfs(px)

while True:

    n,m = map(int,input().split())

    if (n,m) == (0,0):
        break

    start,end = map(int,input().split())
    graph = [[] for _ in range(n)]
    edges = [[inf]*n for _ in range(n)]
    shortcut = set()

    for _ in range(m):
        x,nx,cost = map(int,input().split())
        graph[x].append(nx)
        edges[x][nx] = cost

    V,T = di(start,end)
    if not V[end]:
        print(-1)
    else:
        D = [False]*n
        dfs(end)
        V,T = di(start,end)
        if V[end] == inf:
            print(-1)
        else:
            print(V[end])

 

기존 코드

import heapq as hq
import sys
input = lambda : sys.stdin.readline().rstrip()

inf = 1e9

def di(a,b):
    
    visit = [inf]*n    
    visit[a] = 0
    visit[end] = []

    trace = [-1]*n
    trace[end] = []
    
    heap = [(0,a)]
    while heap:
        c,x = hq.heappop(heap)
        for nx in graph[x]:
            if (x,nx) not in shortcut:
                nc = c + edges[x][nx]
                if nx != end:
                    if nc < visit[nx]:
                        hq.heappush(heap,(nc,nx))
                        visit[nx] = nc
                        trace[nx] = x
                else:
                    visit[end].append(nc)
                    trace[end].append(x)
    return visit,trace

while True:
    
    n,m = map(int,input().split())
    
    if (n,m) == (0,0):
        break
    
    start,end = map(int,input().split())
    graph = [[] for _ in range(n)]
    edges = [[inf]*n for _ in range(n)]
    shortcut = set()

    for _ in range(m):
        x,nx,cost = map(int,input().split())
        graph[x].append(nx)
        edges[x][nx] = cost

    V,T = di(start,end)
    if not V[end]:
        print(-1)
    else:
        min_cost = min(V[end])
        temp = [idx for idx,val in enumerate(V[end]) if val == min_cost]
    
        for idx in temp:
            x,px = end,T[end][idx]
            shortcut.add((px,x))
            while px != start:
                x = px
                px = T[px]
                shortcut.add((px,x))
        
        V,T = di(start,end)
        if not V[end]:
            print(-1)
        else:
            print(min(V[end]))

코멘트

엣지 케이스라기엔 뭔가 당연했는데 너무 생각없이 풀었다.

그래도 디버깅 방향성 잘 잡았고, 재귀에서 시간초과 발생하는거 바로 방문체크 안한거 생각해서 바로 고쳤음.