[BOJ/python]10282번 해킹

백준 10282번 해킹 파이썬

문제 링크 - https://www.acmicpc.net/problem/10282

10282번: 해킹

간단한 다익스트라를 통해 해결 가능한 문제다. 방문 표시를 하며 다익스트라를 실행한 후 방문된 노드를 계산하는 작업을 따로 해주면 된다. 이 때 방문된 노드까지 가는 최단 시간 중 가장 큰 값을 갱신한다.

1. 풀이

의존성의 방향은 간선의 방향이다. 시작 노드는 1개로 지정되어 있다.

• 주어진 시작 노드에서 모든 노드에 대한 최단 경로를 구한다.
• 방문 표시된 노드의 개수를 센다.
• 방문 표시된 노드들에 저장된 dist(누적 비용)값 중 가장 큰 값을 갱신한다.

2. 코드

#해킹  다익스트라
#  V = 1만, E = 10만 (one way)
from heapq import heappop, heappush

T = int(input())
for _ in range(T):
    n,d,c = map(int, input().split())
    G=[ [] for _ in range(n+1)]
    for _ in range(d):
        a,b,s = map(int,input().split())
        G[b].append([a,s])
        
    INF = float('inf')
    heap=[]
    dist=[INF for _ in range(n+1)]
    visited=[0 for _ in range(n+1)]
    dist[c]=0
    heappush(heap, [0,c])
    
    while heap:
        cost, node = heappop(heap)
        if visited[node]==1:
            continue
        visited[node]=1
        for next, d in G[node]:
            if not visited[next]:
                if dist[next] > cost+d :
                    dist[next] = cost+d
                    heappush(heap, [dist[next],next])
    

    count, time = 0,0
    for c in range(1, n+1):     # 방문완료된 도시의 개수 세기, 방문한 도시들 중 가장 시간이 큰 것(최단거리 중에서 최고거리)
        if visited[c] :
            count+=1
            time = max(time, dist[c])
            
    print(count, time)

3. 새로운 풀이

스터디를 하며 다시 한 번 생각해보았다. 가장 기본적인 다익스트라 문제는 특정 노드까지의 최단 경로를 구하는데 해당 문제는 시작 노드에서 갈 수 있는 모든 경로를 탐색해야 한다. 가능한 모든 경로의 탐색이 끝났을 때 걸린 시간을 출력하면 된다. 즉 다익스트라가 아니라 BFS를 통해 탐색할 수도 있다.

BFS를 통해 모든 경로를 탐색하며 방문 표시가 아닌, next 노드에 저장된 누적 시간 값과 current 노드 값에 저장된 누적 시간값과 next 노드까지 가는 시간을 더해준 값을 비교하며 방문하면 된다.