[백준-Python] 해킹 : 10282번

🥇 Gold4

 

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

 

 

 

 

 

✅ 정답 풀이

from sys import stdin
from heapq import heappop,heappush
input = stdin.readline
t=int(input())

INF=float('inf')

def dijkstra(start):
    dist=[INF]*len(graph)
    dist[start]=0
    q=[(0,start)]

    while q:
        cost,idx=heappop(q)
        if dist[idx]<cost:
            continue

        for adj,d in graph[idx]:
            if cost+d<dist[adj]:
                dist[adj]=cost+d
                heappush(q,(dist[adj],adj))

    return dist


for _ in range(t):
    n,d,c=map(int,input().split())
    graph = [[] for _ in range(n + 1)]

    for _ in range(d):
        a,b,s = map(int, input().split())
        graph[b].append((a,s)) # 역방향으로 넣어줌 (의존과 전염은 역관계)


    #다익스트라
    distance=dijkstra(c) # 해킹당한 컴퓨터 기준 최단거리 리스트
    result=list(filter(lambda x:x!=INF,distance)) # 감염된 컴퓨터=인접
    print(len(result),max(result))

 

✨ 경로는 양방향이 아니지만 감염은 역방향으로 퍼져나가기 때문에 그래프에 값을 넣어줄때 역방향으로 넣어주면 된다.

그렇게되면, 감염된 컴퓨터의 개수도 다익스트라 결과값으로 얻은 최단거리 중 초기값 inf가 아닌값으로 쉽게 구할 수 있다.

 

 

출력
각 테스트 케이스마다 한 줄에 걸쳐 총 감염되는 컴퓨터 수, 마지막 컴퓨터가 감염되기까지 걸리는 시간을 공백으로 구분지어 출력한다.

 

나는 마지막 컴퓨가 감염되기까지 걸리는 시간을 마지막 번호(n)번 컴퓨터까지 감염되는 시간을 구하는것으로 이해했다..🙄

그래서 계속 distance[n]으로 감염된 컴퓨터부터, n번까지의 최단경로를 출력하니 오답이 나온것이였다ㅠㅠ

의도한지는 몰라도 테스트케이스마저 모두 성립되길래 계속 왜 안돼를 외치고 있었다...😖

 

 

 

❎ 1차 풀이

from sys import stdin
from heapq import heappop,heappush
input = stdin.readline
t=int(input())

INF=float('inf')

def dijkstra(start):
    dist=[INF]*len(graph)
    dist[start]=0
    q=[(0,start)]

    while q:
        cost,idx=heappop(q)
        if dist[idx]<cost:
            continue

        for adj,d in graph[idx]:
            if cost+d<dist[adj]:
                dist[adj]=cost+d
                count[adj]+=count[idx]+1
                heappush(q,(dist[adj],adj))
    return dist,count


for _ in range(t):
    n,d,c=map(int,input().split())
    graph = [[] for _ in range(n + 1)]
    count=[0]*(n+1)

    for _ in range(d):
        a,b,s = map(int, input().split())
        graph[a].append((b,s)) #(노드번호,cost)


    #다익스트라
    distance,cnt=dijkstra(n) # 해킹당한 컴퓨터 기준 최단거리 리스트

    print(cnt[1],distance[c] if distance[c]!=INF else 0)

 

 

 

처음 풀이했던 방식은 마지막 컴퓨터를 기준으로 다익스트라를 통해 얻은 거리 배열에서 감염된 컴퓨터까지의 경로를 구하는식으로 문제를 풀었다. 문제를 잘못 이해했기 때문에 출발점을 마지막번호 컴퓨터로 하면되기에, 저런 방식을 떠올렸다......

 

아직 처음 풀어서 그런지 역방향을 생각을 미처 못하는것 같다. 많이 풀어보면 괜찮아지겠지라는 희망을 가지고 화이팅!