최소 스패닝 트리를 구하는 알고리즘 중 하나. 최소 스패닝 트리는 사이클이 없는 트리의 형태로 만들고, 간선의 가중치가 최소가 되는 형태를 말한다 프림 알고리즘은 총 4가지의 단계로 구성된다 1. 시작 정점을 잡고 큐에 넣는다 2. 큐에서 pop하고, 해당 정점과 간선을 조사하면서 최소값을 고른다 3. 선택한 간선은 큐에 넣는다 4. 2번을 반복 최솟값을 가지는 간선을 찾기 위해서 매번 정렬을 해야기 때문에 힙으로 구성된 우선순위 큐를 사용하는 것이 시간복잡도에서 뛰어나게 된다 모든 정점에 대해서 살펴봐야 하므로 O(V) 간선을 탐색하는데 힙을 사용하므로 O(logE), 따라서 프림 알고리즘의 시간 복잡도는 O(VlogE)

BFS 고급문제 1. 맵에 대한 정보를 넣는다 2. 나이트는 총 8방향, 룩은 십자가 방향으로 이동, 비숍은 대각선 방향으로 이동 3. 1초에 할 수 있는 일은 1. 말을 바꾸거나 2. 기존 말로 이동 4. dist 배열을 [종류][x][y][번호]로 해서 이동을 할 때 다음 번호가 아니면 계속 이전 번호로 처리해야 한다 문제: https://www.acmicpc.net/problem/16959 https://github.com/surinoel/boj/blob/master/16959.cpp

Critical Path라고 불리는 알고리즘으로, 위상 정렬을 기반으로 시작한다 해당 알고리즘의 목적은 시작점에서 도착점으로 가는 경로가 몇개가 있는 것이 구하는 것이다 위상 정렬을 통해서 각 노드마다 최대로 걸리는 시간을 구할 수 있고, 다시 도착점에서 bfs를 하면서 노드의 거리가 각 노드 max 시간의 거리의 차와 같은지 비교할 수 있다 단, 각 노드는 여러 번 방문할 수 있다. 만일 각 도로의 길이가 모두 같은 상태라면 1은 2번을 방문해야 한다. 따라서 노드는 계속 방문하되 큐에는 한 번만 넣어주는 것이 맞다 문제: https://www.acmicpc.net/problem/1948 https://github.com/surinoel/boj/blob/master/1948.cpp

DAG 문제로, 시간을 가장 늦게끝나는 ind 중 하나의 시간 + buildtime이어야만 한다 문제: https://www.acmicpc.net/problem/1516 https://github.com/surinoel/boj/blob/master/1516.cpp

순서가 정해져있는 작업 순서에 따라서 끝내야 하는 문제 A 작업에 m개에 선수작업이 있다면 A 작업이 끝나려면 A 작업시간 + 선수 m개 중에 가장 늦은 시간이어야만 작업을 정상적으로 마칠 수 있게 된다 문제: https://www.acmicpc.net/problem/2056 소스코드: https://github.com/surinoel/boj/blob/master/2056.cpp

순서가 정해져있는 DAG로, 위상정렬로 해결할 수 있다. 단, 문제 난이도가 쉬운 순서로 풀어야 하는 조건으로 인해 매번 정렬을 해야 한다 매번 정렬을 해야므로, 우선순위 큐로 사용해야하고, 기본 정렬이 내림차순으로 greater로 정렬을 대체해야 한다 문제: https://www.acmicpc.net/problem/1766 소스코드: https://github.com/surinoel/boj/blob/master/1766.cpp