[백준 10282 C++] 해킹

오늘은 백준(BOJ) 10282번 해킹 문제에 대해 다뤄볼 예정이다.

해킹 문제 링크 (백준(BOJ) 10282번 문제): https://www.acmicpc.net/problem/10282

10282번: 해킹

 

문제 설명

백준 10282번 해킹 문제는 여러 개의 컴퓨터가 존재하는데 그 중 특정 컴퓨터(A)가 해킹 당했을 경우, 컴퓨터 A에 의존하고 있는 다른 컴퓨터들도 해킹을 당하게 되는데, 이 때 해킹 당한 컴퓨터의 수와 마지막 컴퓨터가 감영 되기 까지 걸리는 시간을 구하는 문제이다. 

 

문제 풀이 

백준 10282번 해킹 문제를 이해하고 나면, 특정 컴퓨터(A)에서 다른 컴퓨터로 감염될 때 최단 거리로 감염이 되기 때문에 다익스트라 알고리즘을 사용해야함을 알 수 있을 것이다. 

 

해당 문제의 핵심은 서로 컴퓨터 간에 의존성을 연결해줄 때, a, b, s 를 입력 받을 때 b -> a 방향을 가리키도록 해주는 것입니다. 

추가적으로, 마지막 컴퓨터가 감염되는 시간을 구해주면 문제를 해결 할 수 있게된다. 

 

이를 코드로 나타내면, 아래와 같이 나타낼 수 있다.