본문 바로가기
반응형

dfs48

유니티 - 다익스트라를 이용하여 최단 경로 이동하기 (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 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.
BOJ 23290 : 마법사 상어와 복제 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) https://www.acmicpc.net/problem/23290 먼저, 문제 아래에 설명된 상어의 이동 방법에 대해 구현해보자. 상어의 이동 방법은 상하좌우 = 1, 2, 3, 4 중 3개를 선택하는 중복 조합이다 따라서 43 = 64가지 방법을 미리 구현해둔다. N과 M (4) - 중복 조합 코드에서 outputList를 고치면 된다. 상하좌우에 대한 경우의 수는 moveList에 저장해둔다. typedef struct st2 { int move[3]; }MOVE; MOVE moveList[70]; int mcnt; int list[10]; void outputList() { //for (int i .. 2021. 11. 6.
BOJ 1707 : 이분 그래프 (vector) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/1707 메모리 풀을 이용하였던 이분 그래프 문제를 vector를 이용해 풀어보자. 메모리 풀을 위해 사용하였던 아래의 구조체와 HEAD, POOL, pcnt는 더이상 필요가 없다. /* before */ typedef struct st { int node; struct st *next; }NODE; NODE HEAD[20200]; NODE POOL[202000 * 2]; int pcnt; NODE 구조체에 필요한 것은 정수 node였으므로, 아래의 head에 대한 vector들만 선언하면 된다. /* after */ vector HEAD[20200]; 메모리 풀을 초기화하기 위해 pcnt는 0으로 만들었고, HEAD의 nex.. 2021. 6. 17.
SWEA 1949 : 등산로 조성 (모의 SW 역량테스트) 삼성 A형 전체 링크 모의 SW 역량테스트 문제집 등산로 조성 링크 좌표를 저장하기 위한 RC 구조체를 선언한다. MAP의 주변을 벽(-1)으로 만들고 (1, 1)부터 입력을 받는다. 입력을 받으면서 가장 높은 봉우리를 찾는다. 그리고 다시 MAP을 돌면서 가장 높은 봉우리를 start 배열에 담는다. #define MAX (10 + 5) int T, N, K; int MAP[MAX][MAX]; int visit[MAX][MAX]; typedef struct st { int r; int c; }RC; RC start[MAX * MAX]; int scnt; void input() { int max; scanf("%d %d", &N, &K); for (int r = 0; r 2021. 5. 23.
BOJ 1939 : 중량제한 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1939 문제의 답이 되는 최대 중량을 X라고 하자. 그리고 두 섬이 연결되어 있는 것은 DFS를 이용하자. 섬 1과 섬 2가 중량 X로 다리를 건널 수 있다면, DFS(X, 섬 1)은 섬 2로 연결된다. 그러면 DFS(X, 섬 1)은 true다. DFS(X + 1, 섬 1)은 반드시 false가 된다. 이유는 문제의 답이 되는 최대 중량이 X이므로, X + 1의 중량을 견딜 다리가 없기 때문이다. 반대로 DFS(X - 1, 섬 1)은 반드시 true가 된다. 중량 X를 견디는 다리는 최대 중량 X보다 작은 값도 견딜 수 있기 때문이다. 따라서 정답 X에 대해 X보다 작거나 같은 값은 섬을 연결할 수 있고, X보다 큰 값은.. 2021. 5. 22.
SWEA 2105 : 디저트 카페 (모의 SW 역량테스트) 삼성 A형 전체 링크 모의 SW 역량테스트 문제집 디저트 카페 링크 MAP의 좌표는 (1, 1)부터 시작하도록 입력을 받는다. int T, N; int MAP[MAX][MAX]; void input() { scanf("%d", &N); for (int r = 1; r 2021. 5. 17.
SWEA 2112 : 보호 필름 (모의 SW 역량테스트) 삼성 A형 전체 링크 모의 SW 역량테스트 문제집 보호 필름 문제에서 요구한 대로 약품을 투입한다. 이 때, DFS에서 매번 MAP을 copy하는 비용을 낮추기 위해 약간의 테크닉을 사용할 수 있다. 특성 A가 0, B가 1이므로, MAP[1]에는 0을, MAP[2]에는 1을 저장해둔다. int MAP[3][MAX][MAX]; int list[MAX]; void input() { scanf("%d %d %d", &D, &W, &K); for (int r = 1; r 2021. 5. 14.
SWEA 2383 : 점심 식사시간 (모의 SW 역량테스트) 삼성 A형 전체 링크 모의 SW 역량테스트 문제집 점심 식사시간 시뮬레이션 문제는 그대로 잘 구현하면 된다. 먼저 좌표를 저장할 RC 구조체를 선언한다. people배열에는 사람의 좌표를, stair 배열에는 계단의 좌표를 저장한다. list는 DFS로 사람을 나눌 때 사용한다. 2차원 배열 distance는 계단과 사람 사이의 거리이다. distance[1][3]은 1번 계단과 3번 사람과의 사이를 의미한다. stairLength는 계단을 내려가 이동이 완료되는 시간을 저장한다. (1/2번 계단에 대한 시간) #define MAX (10 + 5) int T, N; int MAP[MAX][MAX]; int list[MAX]; typedef struct st { int r; int c; }RC; RC pe.. 2021. 5. 7.
반응형

티스토리툴바