728x90
반응형
※ 문제링크
10282번: 해킹
최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면
www.acmicpc.net
해당문제는 다익스트라 알고리즘을 활용하여 풀 수 있는 문제였다. 입력받은 값들로 그래프를 구현하고 다익스트라로 최단거리를 구해준 후 이어져 있는 컴퓨터의 수와 최대 시간만 출력해주면 되었기에 생각보다 쉽게 해결할 수 있었다. 자세한 풀이방법과 코드는 아래와 같다.
1. 입력받은 값들과 2차원 리스트를 활용하여 그래프를 구현해준다.
2. 각각의 컴퓨터들로 갈 수 있는 최단시간을 구하기 위한 다익스트라 함수를 작성해준다.
3. 입력받은 값들로 결과값을 출력해준다.
import sys
from heapq import heappush, heappop
def dijkstra(start):
heap = []
dp = [float('inf') for _ in range(n+1)]
dp[start] = 0
heappush(heap, [0 ,start])
while heap:
t, n_c = heappop(heap)
for n_c_t, n_n_c in graph[n_c]:
n_t = t + n_c_t
if n_t < dp[n_n_c]:
dp[n_n_c] = n_t
heappush(heap, [n_t, n_n_c])
check = dp.count(float('inf')) - 1
ans1 = n - check
ans2 = sorted(dp)[-check-2]
return ans1, ans2
# input = sys.stdin.readline
T = int(input())
for _ in range(T):
n, d, c = map(int, input().split()) # n: 컴퓨터의 수 / d: 의존성의 개수 / c: 해킹된 컴퓨터
graph = [[] for _ in range(n+1)]
for _ in range(d):
a, b, s = map(int, input().split())
graph[b].append([s, a])
print(*dijkstra(c))
P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.
728x90
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 11057번 오르막수 / 사용언어 : 파이썬(python) (0) | 2022.02.07 |
---|---|
[BOJ] 11726번 2xn 타일링 / 사용언어 : 파이썬(python) (0) | 2022.02.01 |
[BOJ] 1854번 K번째 최단경로 찾기 / 사용언어 : 파이썬(python) (0) | 2022.01.30 |
[BOJ] 2665번 미로만들기 / 사용언어 : 파이썬(python) (0) | 2022.01.30 |
[BOJ] 1216번 알고스팟 / 사용언어 : 파이썬(python) (0) | 2022.01.29 |
댓글