-
https://www.acmicpc.net/problem/10282
https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2010282
해당 문제는 컴퓨터 수와 의존성과 시간이 주어졌을 때
시작 컴퓨터로부터 감염시킬 수 있는 컴퓨터의 개수와 최대로 걸리는 시간을 구하는 문제다.
해당 문제는 다익스트라 알고리즘을 이용해서 해결했으며, 처음에 문제를 읽고
양방향으로 생각해서 문제를 해결했더니 첫 번째 테케 결과가 3 5가 나왔었고,
문제를 다시 읽어보니 입력 조건에서 컴퓨터 b가 감염되면 s초 후 컴퓨터 a도 감염됨을 뜻한다.
라는 조건을 확인하게 되었고, 이에 맞춰 b에서 a로 가리키도록 수정해서 문제를 해결할 수 있었다.
입력 처리를 하고 우선순위 큐에 대해서는 람다식을 이용해 정렬해주었다.
리스트에 의존성 정보를 넣어줄 때 b에서 a로 가리키도록 리스트에 추가하여 준 뒤,
다익스트라 알고리즘을 적용하였고 이후 cost배열의 값을 체크해서
max값인 경우 방문할 수 없는 곳이고, 나머지 값들에 대해서 카운트 및 max값을 찾아 출력해준다.
(시작 컴퓨터도 체크해야 하기 때문에 0인 값을 거르지 않음)
728x90'알고리즘 > Baekjoon' 카테고리의 다른 글
Baekjoon 1965 상자넣기 JAVA (0) 2021.11.16 Baekjoon 13414 수강신청 JAVA (0) 2021.11.15 Baekjoon 15723 n단 논법 JAVA (0) 2021.11.15 Baekjoon 10825 국영수 JAVA (0) 2021.11.15 Baekjoon 2210 숫자판 점프 JAVA (0) 2021.11.15 댓글