[Python][백준 10282][다익스트라] 해킹 - 컴도리돌이

10282번: 해킹

---

풀이 과정

 

해당 문제는 정말 대표적인 다익스트라 문제인 거 같다.. 문제를 해결하는데 몇 분도 안 걸린 기분 좋은 문제였다. 😊 

 

1. 입력받은 T만큼 반복문을 돌린다.

2. 입력받은 컴퓨터 수(n), 의존성 관계(d), 감염된 컴퓨터 번호(c)를 입력받는다.

3. 필자는 의존성 관계를 표현하는 2차원 배열을 computers 이름으로 할당해주었다. 그리고 감염된 컴퓨터가 있을 경우 해당 컴퓨터가 몇 초 후에 감염되는지 확인하기 위하여 infection이라는 이름으로 1차원 배열을 큰 값으로 할당해주었다.

4. 입력받은 d만큼 반복문을 돌린다. 의존 관계가 있는 a, b 그리고 감염 시간 s를 입력받는다.

5. 감염된 시간이 적은 값부터 처리하기 위하여 min heap을 사용하였고, heap이라는 배열에 [감염된 시간, 감염된 컴퓨터 번호]로 입력된다. 초기에는 감염된 컴퓨터 c번을 넣어주었다. 그리고 감염된 c번 컴퓨터는 0초로 infection에  값을 변경해주었다.

6. 감염된 시간이 짧은 컴퓨터부터 처리된다. 현재 컴퓨터(cur)와 의존 관계가 있는 컴퓨터(next)의 시간의 합이 infection에 저장되어 있는 시간보다 짧을 경우 min heap에 다시 넣어준다. 그때 infection의 시간도 업데이트해준다.

7. INF 값이 아닌 infection의 값은 모두 감염된 것이기 때문에 카운팅 해주고, 그중에 max 시간을 찾아 준다.

---

풀이 과정

 

import sys,heapq; input =sys.stdin.readline ; INF = 987654321

# 테스트 케이스 T 만큼 반복 
for _ in range(int(input())) :
  # 컴퓨터 수, 의존성 개수, 해킹 당한 컴퓨터 번호 
  n,d,c = map(int,input().split())

  # 컴퓨터 의존성 배열 n만큼 할당
  computers = [[] for _ in range(n)]

  # 몇 초후에 컴퓨터가 감염되는지 확인하는 배열 (INF으로 초기화)
  infection = [INF for _ in range(n)]

  # d만큼 반복해서 의존 관계 a,b 와 시간 s를 입력
  for _ in range(d) :
    a,b,s = map(int,input().split())
    computers[b-1].append([a-1,s])

  # 시간이 작은 값을 먼저 처리하기 위하여 min heap을 사용 예정
  heap = [[0,c-1]]

  # 감염된 컴퓨터는 시간이 0초에 감염
  infection[c-1] = 0

  # min heap
  while heap :
    # 현재 감염된 시간, 현재 컴퓨터 번호
    curTime,cur = heapq.heappop(heap)

    # 현재 컴퓨터와 의존 관계가 있는 번호, 현재 컴퓨터가 감염되면 nextTime초 후 감염
    for next,nextTime in computers[cur] :

      # 다음 컴퓨터 감염 시간 = 다음 컴퓨터 감염 시간 + 현재 컴퓨터 감염 시간
      nextTime += curTime
      # 해당 컴퓨터 걸린 시간보다 빠르면 min heap에 추가 및 시간 업데이트
      if nextTime < infection[next]  :
        infection[next] = nextTime
        heapq.heappush(heap,[nextTime,next])
  cnt = 0 # 감염된 컴퓨터 수 찾기
  ans = -1 # INF를 제외한 max 시간 찾기
  for value in infection :
    if value != INF : 
      cnt +=1
      ans = max(ans,value)
  print(cnt,ans)