[백준] 28283 해킹 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/28283
• 🔑 BFS
  • 보안 시스템이 설치되는 컴퓨터로부터 탐색을 시작한다.
  • 각 컴퓨터까지의 깊이를 방문 배열에 저장한다.
    • 보안 시스템이 각 컴퓨터로 뻗어 나가는 순서
  • 탐색 종료 후, 방문 안 했고 이 컴퓨터에서 훔칠 수 있는 돈이 있는 경우는 -1을 출력 (무한히 훔칠 수 있음)
  • 위 조건에 해당하지 않으면
  • 깊이가 저장된 방문배열에 각 컴퓨터마다 (깊이 * 이 컴퓨터에서 훔칠 수 있는 돈) 계산을 한다.
  • 내림차순으로 정렬해서 가장 많은 돈을 훔친 x개의 합을 구한다.
  • 끝 ✨

 

from collections import defaultdict, deque
import sys
input = sys.stdin.readline

n, m, x, y = map(int, input().split())
money = list(map(int, input().split()))

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

security = list(map(int, input().split()))

visit = [0] * (n+1)
q = deque([])

for i in security:      # 보안 시스템 설치되는 컴퓨터 큐에 넣기
    visit[i] = 1
    q.append([i, 1])    # [컴퓨터 번호, 깊이]

while q:    # BFS
    now_node, d = q.popleft()

    for next_node in graph[now_node]:
        if visit[next_node] == 0:
            visit[next_node] = d + 1
            q.append([next_node, d + 1])

visit.pop(0)    # 필요없는 제일 앞에 요소 없앴음

for i in range(len(visit)):
    if visit[i] == 0 and money[i] != 0:     # 보안 시스템 설치가 안 됐고 훔칠 수 있는 돈이 있으면
        print(-1)                           # 무한히 훔칠 수 있으니까 -1
        exit()

for i in range(n):                          # 각 컴퓨터마다 얼마나 훔칠 수 있는가?
    visit[i] = (visit[i]-1) * money[i]

visit.sort(reverse=True)                    # 훔칠 수 있는 돈이 많은 순으로 정렬

answer = 0
for i in range(x):                          # x대의 컴퓨터 선택
    answer += visit[i]

print(answer)