Jonyo Programming

[BOJ 10282(G4) 리뷰] 단순히 몇대의 컴퓨터가 감염되는지 구하는 문제가 아닌, 감염이 가능한 모든 컴퓨터가 감염되는 최단 시간을 구해야 한다. 그러므로 이 문제를 해결하기 위해서는 다익스트라 알고리즘을 사용해야 한다. 시작 컴퓨터가 주어졌으니 시작컴퓨터로부터 다익스트라 알고리즘을 수행한다. 그 후에 시간이 기록된 DIST배열 전체를 확인하여, 거리가 갱신된 노드들이 감염된 컴퓨터의 숫자가 된다. 그리고 감염이 되는 시간은 항상 0보다크므로 DIST배열중 가장 큰 값이 모든 컴퓨터가 감염되는 최단경로가 될 것이다. /* 21.02.02 BOJ : 10282 해킹 (https://www.acmicpc.net/problem/10282) 다익스트라 알고리즘 */ #include using namesp..

[BOJ 1854(P5) 리뷰] 다익스트라 알고리즘 + 우선순위 큐를 이용하여 풀었다. 다익스트라 알고리즘을 통해 1번노드부터 N번노드까지의 최단경로를 구할 수 있다. 이때, 최단경로만 저장하는 것이 아니라 가능한 모든 경로를 저장하면 된다. K번째 최단경로를 찾기위해 정렬된 모든 경로중 K번째에 있는 값을 출력하면 될것이라 생각했지만 그렇지 않았다. 가능한 모든 경로를 담을 수가 없기에 필요한 경로들만 담아야 한다. 이때 우선순위큐가 필요하다. 우선순위 큐를 내림차순으로 정렬한다면 큐의 SIZE가 K일때 큐의 TOP에 있는 값이 K번째로 큰값이라는것을 알 수 있다. 이 원리를 이용하면 된다. 새로운 경로가 계산될때마다 큐의 사이즈를 확인하여 큐에 넣는작업을한다. 큐의 사이즈가 K보다 작다면, 아직 K번..