작심 24/7

최소힙, 루트 노드를 0번으로 지정. (1번으로 지정하는 게 더 편리하긴 함) int heap[100]; int heapSize = 0; void init(){ heapSize = 0; } int push(int value){ if (heapSize == 100) return 0; // 최대 사이즈를 넘어가면 나가리 heap[heapSize] = value; // 마지막 노드에 값 추가 // 마지막 노드에 추가한 값을 올바른 위치로 옮김 int current = heapSize; // 현재 위치 저장 while(current > 0 && heap[(current - 1) / 2] > heap[current]){ // 최소힙인데 부모 > 자식이면 안 되니까 바꿔주기 // 부모랑 자식 swap int tmp..

1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net graph[정점 A] = (정점 B, A→B 비용) 으로 값을 입력받은 후 dist[i] = K→i 비용 을 저장한다. 처음에는 모두 무한대로 저장해 두고 K→K일 때만 0을 저장해준다. 우선순위 큐 pq는 비용을 기준으로 오름차순 정렬된다. 제일 처음엔 시작점 K와 K→K 비용 0을 넣어준다. pq의 top에 있는 정점을 mid라 표현할 때, mid에서 바로 갈 수 있는 정점들 to를 탐색해주며 시작점 K→to 비용보다 시작점 K→m..

16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net BFS를 이용하여 상어 크기와 같은 물고기가 있거나 빈칸인 공간으로 이동하면서 상어 크기보다 작은 물고기를 발견하면 우선순위 큐에 BFS의 깊이(걸린 시간), x좌표, y좌표를 넣어준다. 탐색을 다 마치고 돌아와 우선순위 큐가 비어있으면 먹을 수 있는 물고기가 없는 것이므로 종료 후 최종 시간 출력, 비어있지 않으면 큐 안에서 1. 깊이(걸린 시간)가 가장 작은 순서대로 2. x좌표가 가장 위에 있는 순서대로 3. y좌표가 가장 왼쪽에 있는 순서대로 오..