반응형 priority queue29 BOJ 6593 : 상범 빌딩 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/6593 참고 - BOJ 11779 : 최소비용 구하기 2 최단 경로는 BOJ 11779 : 최소비용 구하기 2에서 사용한 다익스트라를 이용해서 구할 수 있다. 상범 빌딩은 다익스트라를 3차원에 적용하면 된다. tc가 여러 개이므로 매 tc마다 dist를 INF로 visit을 0으로 초기화한다. for (i = 1; i 2023. 3. 26. BOJ 1504 : 특정한 최단 경로 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1504 참고 - BOJ 11779 : 최소비용 구하기 2 최단 경로는 BOJ 11779 : 최소비용 구하기 2에서 사용한 다익스트라를 이용해서 구할 수 있다. 이 문제에서는 임의의 두 정점(n1, n2)을 통과하는 최단 경로를 구하려고 하므로, 다익스트라를 여러 번 사용하면 된다. 즉, 출발점 - n1 - n2 - 도착점에 대해 각각 다익스트라를 이용해 거리를 구한다. 여기서 n1이 반드시 n2 보다 먼저 도착해야할 이유는 없다. n1 - n2와 n2 - n1 경로를 비교해서 더 작은 경우가 정답이 된다. ans1 = getDijkstra(1, n1) + getDijkstra(n1, n2) + getDijkstra(n2,.. 2023. 3. 25. 유니티 - 다익스트라를 이용하여 최단 경로 이동하기 (Move the Shortest Path using Dijkstra) Unity 전체 링크 다익스트라(데이크스트라)를 이용하면 최소 경로를 찾을 수 있다. 그리고 최소 경로를 찾을 때 해당 경로를 저장해두면 경로도 구할 수 있다. 관련 알고리즘은 아래 링크를 참고하자. - BOJ 11779 : 최소비용 구하기 2 (최단 경로 기억) - BOJ 1261 : 알고스팟 (2차원 배열 다익스트라) 그리드 기반으로 맵을 탐색한 후, 빨간 큐브 (0, 1, 0)가 보라색 큐브 (-7, 1, 4)로 가기 위한 최단 경로를 찾아보고 직접 이동도 해보자. 그리드 보다 높게 보이기 위해 y = 1로 설정하였다. 최단 경로를 찾으면 아래와 같다. Invoke는 필요 없으므로 원래대로 돌린다. 아래의 코드에서 다익스트라를 시작한다. 다익스트라 관련 코드는 #region Dijkstra Algo.. 2022. 7. 17. BOJ 1261 : 알고스팟 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1261 ※ 다익스트라를 이용하여 최단 경로 이동하기는 유니티에서 확인할 수 있다. BOJ 11779 : 최소비용 구하기 2의 다익스크라(데이크스트라) 알고리즘을 2차원 배열에서 사용하면 된다. 2차원 배열의 각 인접한 노드는 dr, dc 배열로 탐색한다. int dr[] = { 0, 1, 0, -1 }; int dc[] = { 1, 0, -1, 0 }; 그리고 벽(1)이 비용이 된다. int MAP[110][110]; 거리를 저장할 2차원 배열과 방문 여부를 체크하는 배열, 그리고 최소 힙을 만든다. int distance[110][110]; int visit[110][110]; typedef struct st2 { in.. 2022. 7. 17. BOJ 11779 : 최소비용 구하기 2 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/11779 ※ 다익스트라를 이용하여 최단 경로 이동하기는 유니티에서 확인할 수 있다. 출발 도시에서 도착 도시까지 가는데 드는 최소 비용과 도시의 개수 그리고 최소 비용이 되는 경로도 출력해야 한다. 메모리 풀 방식으로 각 도시 간의 연결과 가중치를 저장한다. typedef struct st { int value; int weight; struct st *next; }NODE; NODE HEAD[1010]; NODE POOL[100100]; int pcnt; void Make(int p, int c, int w) { NODE *nd = &POOL[pcnt++]; nd->value = c; nd->weight = w; nd-.. 2022. 7. 16. Indexed Priority Queue - 우선순위 큐의 임의 원소 갱신, 변경 (update) 삼성 B형 전체 링크 참고 - 우선순위 큐 Priority Queue - 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기 - 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기 - 우선순위 큐 임의 원소 삭제 - 우선순위 큐 임의 원소 삭제 최적화 - 우선순위 큐 임의 원소 갱신, 변경 [수정] 항상감사합니다.님의 의견에 따라 방어코드가 필요한 것을 확인하였습니다. 제 코드는 update할 index = updatehn이 updatehn * 2 == hn(힙의 현재 크기)인 경우 문제가 발생합니다. PRO 시험에 제 코드를 사용하시는 분들은 아래 추가된 글 참고 부탁드립니다. Reference code ver Indexed Priority Queue, Heap - updat.. 2022. 1. 13. BOJ 14427 : 수열과 쿼리 15 (Reference) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/14427 B형에서는 Reference로 우선순위 큐 code가 주어진다. 하지만 STL(priority_queue) 사용이 가능하더라도, 갱신이 가능한 우선순위 큐는 직접 만들어야 한다. 여기서는 Reference 우선순위 큐로 문제를 풀었다. (Indexed Priority Queue, Heap) 해설은 이전 글을 참고하자. #include int N, M; typedef struct st { int value; int id; }HEAP; HEAP heap[100100]; int heapIdx[100100]; int heapSize; int isMin(HEAP a, HEAP b) { if (a.value < b.value).. 2021. 7. 3. BOJ 14427 : 수열과 쿼리 15 with 우선순위 큐 삼성 B형 전체 링크 https://www.acmicpc.net/problem/14427 참고 - BOJ 14427 : 수열과 쿼리 15 with 세그먼트 트리 우선순위 큐의 갱신을 이용하여 문제를 풀 수 있다. update를 위해 우선순위 큐를 최악의 값으로 초기화한다. for (int i = 0; i < 200100 /* heap size */; i++) heap[i].id = heap[i].value = 0x7fff0000; 처음의 값들은 순서대로 A1 ~ AN 이므로 heapIdx(id)를 각각 i = 1 ~ N으로 본다. for (int i = 1; i 1; i /= 2) { if (isMin(heap[i / 2], heap[i])) break; tmp = heap[i]; heap[i] = he.. 2021. 7. 3. BOJ 10825 : 국영수 (priority_queue, compare) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/10825 이번에는 BOJ 10825 : 국영수 문제를 STL로 풀어보자. 즉, 구조체에 대한 우선순위를 compare에 적용시켜보자. 먼저 HEAP의 char name[15]; 는 string으로 변경하였다. typedef struct st { string name; // char name[15]; int kr; int en; int math; }HEAP; 국영수 문제에서 국어, 영어, 수학 점수에 대한 우선순위는 아래와 같이 판단하였다. int isMin(HEAP a, HEAP b) { if (a.kr > b.kr) return 1; if (a.kr == b.kr) { if (a.en < b.en) return 1; if .. 2021. 6. 21. 이전 1 2 3 4 다음 반응형
