반응형 데이크스트라4 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. 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. 이전 1 다음 반응형
