Baekjoon 10282 해킹 JAVA

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

10282번: 해킹

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2010282

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 컴퓨터 수와 의존성과 시간이 주어졌을 때

시작 컴퓨터로부터 감염시킬 수 있는 컴퓨터의 개수와 최대로 걸리는 시간을 구하는 문제다.

 

해당 문제는 다익스트라 알고리즘을 이용해서 해결했으며, 처음에 문제를 읽고

양방향으로 생각해서 문제를 해결했더니 첫 번째 테케 결과가 3 5가 나왔었고,

문제를 다시 읽어보니 입력 조건에서 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다. 

라는 조건을 확인하게 되었고, 이에 맞춰 b에서 a로 가리키도록 수정해서 문제를 해결할 수 있었다.

 

입력 처리를 하고 우선순위 큐에 대해서는 람다식을 이용해 정렬해주었다.

리스트에 의존성 정보를 넣어줄 때 b에서 a로 가리키도록 리스트에 추가하여 준 뒤,

다익스트라 알고리즘을 적용하였고 이후 cost배열의 값을 체크해서

max값인 경우 방문할 수 없는 곳이고, 나머지 값들에 대해서 카운트 및 max값을 찾아 출력해준다.

(시작 컴퓨터도 체크해야 하기 때문에 0인 값을 거르지 않음)