반응형 깊이우선탐색4 [C/C++] 백준 #2573 빙산(깊이 우선 탐색) 이번 문제는 보다 좋은 알고리즘을 택하기 보다는 구현을 위주로 하였습니다. 깊이 우선 탐색은 섬의 개수가 몇개인지 판단하기 위해서 사용을 하였습니다. 문제 링크입니다. https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제는 빙하가 같은 높이만큼 녹을 때, 한덩어리의 빙하가 두덩어리 이상이 되는 최소 녹는 높이를 구하는 것입니다. 구현 자체는 간단합니다. 빙하가 녹는 높이에 따라서 빙하가 두개가 될 때의 높이를 출력하게 하였습니다. 제가 구.. 2023. 7. 30. [C/C++] 백준 #2367 파티(포드-폴커슨 알고리즘) 이번 문제는 파티에서 음식을 준비할 때, 음식의 종류와 할 수 있는 음식 종류, 그리고 가져올 수 있는 음식의 개수가 제한되어 있을 때, 최대한의 음식을 준비하는 것을 목표로 하는 내용입니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2367 2367번: 파티 첫째 줄에는 N, K, D가 주어진다. 다음 줄에는 D개의 정수가 주어지는데, 이는 각 음식의 종류마다 가져올 수 있는 양의 제한을 의미한다. 이 값은 N보다 작거나 같은 음이 아닌 정수이다. 다음 N개 www.acmicpc.net 이 문제를 풀기 위해서는 최대 유량 알고리즘을 알아야 합니다. 최대 유량은 제한 조건이 있을 때, 그 조건을 지키는 한도 내에서 최대의 결과를 얻을 때 사용됩니다. 최대유량과 관련되어.. 2023. 4. 28. [C/C++] 백준 #2146 다리 만들기(DFS, BFS) 이번 문제는 최단거리를 찾는 문제이긴 하지만, 이동하는데 드는 비용이 항상 같기 때문에 너비 우선 탐색을 사용하면 되는 문제입니다. 문제는 아래의 링크입니다. https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 이 문제를 풀 때에는 두 단계를 걸쳐서 풀었습니다. 일단 섬마다 고유한 아이디를 부여하기 위해서 깊이우선탐색(DFS)을 이용해서 고유 아이디를 붙였습니다. 다음으로는 모든 섬에 대해서 다리를 놓기 위한 최단 거리를 구하는 작업을 하였습니다. 이 .. 2023. 4. 10. [C/C++] 백준 #1981 배열에서 이동(이분탐색) 이번 문제는 보통의 그래프 문제와 다르게 경로상의 최저값과 최고값의 차이가 가장 적게 나오는 경로에서의 그 차이를 출력하는 문제입니다. 최저값과 최고값의 차이를 가지고 다루는 문제이기 때문에 다익스트라 알고리즘과 같은 탐욕 알고리즘 기반을 사용할 수가 없습니다. 제가 접근한 방법은 최고값과 최저값의 차이를 주어지고, 깊이우선 탐색(DFS)을 통해서, 시작점과 끝점까지 가는데, 그 차이를 가지는 경로가 있는지 확인하도록 했습니다. 최고값과 최저값의 차이는 이분탐색을 이용했습니다. 제일 먼저 모든 간선값들의 최저값과 최고값을 찾아서 그 차이값을 상한값으로 하였습니다. 이 값은 반드시 경로가 존재하게 되겠죠. 그리고 경로가 존재할 수 없는 값은 -1이 되겠죠. 모든 간선값이 같은 경우에는 0이 나와야 하니까요.. 2023. 1. 2. 이전 1 다음 728x90
