반응형 Dijkstra7 [코드트리] 개구리의 여행 (삼성 SW 역량테스트 2025 상반기 오전 2번, B형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크삼성 B형 전체 링크 2022 하반기 이후 문제 풀이 시간이 3시간 → 4시간으로 변경,A형 1문제 + B형 문제 1문제가 출제됩니다. 참고 - B형 필수 : 우선순위 큐 Priority Queue- BOJ 11779 : 최소비용 구하기 2- BOJ 6593 : 상범 빌딩 https://www.codetree.ai/ko/frequent-problems/problems/frog-journey/description 현재 개구리의 점프력에서 갈 수 있는 (r, c)의 최소 거리를 dist[jump][r][c]에 저장한다.isMove는 (r, c)에서 (nr, nc)로 이동할 수 있는지 여부를 미리 전처리하는데 사용한다.#def.. 2025. 5. 1. [코드트리] 코드트리 투어 (삼성 SW 역량테스트 2024 상반기 오전 2번, B형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크삼성 B형 전체 링크 2022 하반기 이후 문제 풀이 시간이 3시간 → 4시간으로 변경,A형 1문제 + B형 문제 1문제가 출제됩니다. 참고- B형 필수 : 우선순위 큐 Priority Queue- BOJ 10825 : 국영수- BOJ 11779 : 최소비용 구하기 2 https://www.codetree.ai/training-field/frequent-problems/problems/codetree-tour 코드트리 랜드 건설 모든 도시에 대해 가중치를 INF(= 0x7fff0000)으로 초기화한다.최소거리를 구하는 문제이므로, 여러 간선 중 최소의 가중치만 필요하다.따라서 가장 작은 가중치만 W[v][u] / W[u].. 2024. 8. 11. 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->next = .. 2022. 7. 16. 이전 1 다음 반응형
