[파이썬/python] 백준 - 28283 해킹

문제

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

---

문제 설명

1. 네트워크 안에 N개의 컴퓨터가 존재하며 서로 다른 두 컴퓨터 쌍을 연결하는 M개의 통신망이 존재한다. 
   1. i번째 통신망은 $S_i$번과 $E_i$번 컴퓨터를 잇고 있다. 두 컴퓨터 쌍을 연결하는 통신망은 최대 1개이다.
2. X개의 컴퓨터를 동시에 해킹하여 돈을 얻고자 한다.
   1. i번 컴퓨터를 해킹하면 1분 뒤부터 매분 $A_i$의 돈을 가져올 수 있다.
3. 해킹 후 0.5분부터 $B_1, B_2...B_Y$번 컴퓨터에 보안 시스템이 설치 된다. 보안 프로그램이 설치되고 난 후부터는 돈을 가져올 수 없다.
   1. 보안 시스템은 통신망을 통해 1분마다 연쇄적으로 전파된다.
4. 보안 시스템을 피해 최대한 많은 돈을 얻을 방법을 찾아 최대 금액을 구한다.

 

---

풀이

다익스트라 알고리즘을 통해 문제를 풀이했다.

 

문제의 핵심은 보안 시스템이 특정 컴퓨터에서 시작해 통신망을 따라 1분마다 전파된다는 점이다.

즉, 각 컴퓨터에 보안 시스템이 언제 도달하는지 계산해야 한다.

 

보안 시스템은 여러 컴퓨터에서 동시에 시작되기 때문에 멀티 소스 최단거리 문제로 볼 수 있다.

멀티 소스 다익스트라는 시작할 때 여러가지 정점을 넣고 탐색을 진행하는 알고리즘이다.

따라서 다익스트라를 이용해 각 컴퓨터까지 보안 시스템이 도달하는 최소 시간을 구했다.

 

모든 간선의 가중치는 1이지만, 시작 정점이 여러 개이기 때문에 우선순위 큐를 이용한 다익스트라 방식으로 구현했다.

 

다익스트라를 수행하면 각 컴퓨터에 보안 시스템이 도달하는 시간을 구할 수 있다.

 

이후 각 컴퓨터를 해킹했을 때 얻을 수 있는 돈을 계산했다.

 

컴퓨터를 해킹하면 1분 뒤부터 매분 $A_i$만큼의 돈을 얻을 수 있고,
보안 시스템이 dist[i]분 뒤에 도달한다면 총 $dist[i]*A_i$만큼의 돈을 얻을 수 있다.

 

따라서 각 컴퓨터에서 얻을 수 있는 돈을 계산한 뒤, 가장 큰 값부터 X개를 선택하여 합을 구하도록 구현했다.

 

여기서 예외처리할 부분이 한 가지 존재한다.

 

다익스트라 결과 어떤 컴퓨터는 보안 시스템이 도달하지 못할 수도 있다.
이 경우 이 컴퓨터는 계속 돈을 벌 수 있기 때문에 무한의 돈을 얻을 수 있는 상황이 된다.

 

처음에는 이런 정점이 하나라도 존재하면 무조건 -1을 출력하도록 구현했다.

 

하지만 보안 시스템이 도달하지 않는 컴퓨터라고 하더라도 해당 컴퓨터의 $A_i$값이 0이라면 돈을 벌 수 없다.
즉, 보안 시스템이 오지 않더라도 돈 자체가 발생하지 않기 때문에 무한의 돈이 되는 상황이 아니다.

 

따라서 dist[i]가 INF이며 cost[i]가 0이 아닌 경우에만 -1을 출력하도록 하였다.

 

=> 다른사람들 코드를 봤는데 대부분 BFS로 구현한 것 같다.

BFS로 탐색하면 시간복잡도는 $O(V+E)$정도인데, 내가 푼 방식은 $O(Elog_V)$이라 $log_V$배만큼 지수적으로 커지기 때문에 시간이 더 걸리게 된다.

 

이 문제는 BFS로 풀이하는게 더 옳은 풀이인 것 같다.

---

코드

import sys
import heapq
input = sys.stdin.readline

INF = sys.maxsize
N,M,X,Y = map(int,input().split())
cost = [0] + list(map(int,input().split()))


graph = [[] for _ in range(N+1)]
for i in range(M):
    v1,v2 = map(int,input().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

dist = [INF for _ in range(N+1)]

hq = []
for v1 in list(map(int,input().split())):
    heapq.heappush(hq, (0,v1))
    dist[v1] = 0

def dijkstra():

    while hq:
        cur_dist, v1 = heapq.heappop(hq)

        if dist[v1] < cur_dist:
            continue

        for v2 in graph[v1]:
            if dist[v2] < cur_dist + 1:
                continue

            dist[v2] = cur_dist+1
            heapq.heappush(hq,(dist[v2], v2))
dijkstra()
res = []

for i in range(1,N+1):
    if dist[i] == INF and cost[i] != 0:
        print(-1)
        exit()

    res.append(dist[i]*cost[i]) 
res.sort(reverse = True)

print(sum(res[:X]))

---

시간복잡도

• 다익스트라의 시간복잡도는 $Elog_V$이다. 즉 $E = 500,000, V = 500,000$이므로
• 약 $5*10^5 * log_{10^5} = 10^7$, $O(10^7)$의 시간복잡도를 가진다.