반응형 BFS7 [C/C++] 백준 #3055 탈출(너비 우선 탐색) 백준 온라인 저지 문제 #3055는 “탈출”이라는 제목의 문제로, 주어진 2차원 맵에서 고슴도치가 물을 피하면서 동굴로 탈출하는 경로를 찾는 시뮬레이션 문제입니다. 문제의 주요 포인트는 다음과 같습니다.문제 설명1. 맵 구성: 고슴도치는 S로, 동굴은 D로 표시되어 있습니다. 물은 *로 표시되며 매 시간마다 상하좌우로 확산합니다. 빈 공간은 .로 표현됩니다.2. 목표: 고슴도치는 물이 찰 예정인 칸을 피하면서 최소한의 이동 시간으로 동굴(D)에 도달해야 합니다.3. 제약 조건:• 고슴도치는 한 번에 상하좌우로 한 칸씩 움직일 수 있습니다.• 물은 매 시간마다 고슴도치보다 먼저 확산되어 고슴도치의 경로를 막을 수 있습니다.4. 출력 조건: 고슴도치가 동굴로 탈출할 수 있는 최소 시간을 출력하며, 탈출이 불.. 2024. 11. 7. [C/C++] 백준 #2589 보물섬(너비 우선 탐색) 이번 문제는 너비 우선 탐색을 이용해서 풀었습니다. 플로이드 워샬을 이용해서 풀 수도 있겠지만, 모든 노드가 다 이어진 것이 아니기 때문에 같은 알고리즘 효율이라는 관점에서 너비 우선 탐색을 이용했습니다. https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 문제는 섬안에서 최단거리로 가장 먼 두 점을 찾는 것입니다. 한칸의 거리가 모두 같기 때문에 다익스트라 알고리즘을 사용하지 않고, 너비 우선 탐색을 통해서도 충분합니다. 너비 우선 탐색의 깊이가 가.. 2024. 1. 22. [C/C++] 백준 #2206 벽 부수고 이동하기(너비 우선 탐색) #2206은 평범한 너비 우선 탐색 문제는 아닙니다. 벽을 한번까지는 부실 수 있는 조건이 있기 때문에, 이에 대해서 처리를 해주어야 합니다. 문제의 링크는 다음과 같습니다. https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이 문제는 한번 이동하는데 항상 1이라는 가중치가 있는 그래프이기 때문에, 벽을 뚫고 갈 수 있다는 것을 원칙을 정해서 풀면 됩니다. 1) 벽을 한번 부수고 지나간 길은 음의 값으로 경로값을 적는다... 2023. 4. 16. [C/C++] 백준 #2178 미로 탐색(너비 우선 탐색) 미로 탐색은 대표적인 그래프 탐색과 관련되어 풀 수 있는 문제입니다. 길이 여러개이고, 움직일 때 비용이 똑같다고 한다면, 다익스트라와 같이 우선순위큐를 사용하는 알고리즘을 이용하지 않고, 너비 우선 탐색을 이용해도 됩니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이번 미로 탐색은 최단 경로를 찾아야 한다는 표현이 있지만, 고전적인 미로 탐색 문제입니다. 너비우선탐색 알고리즘을 이용하였습니다. 출발점에서부터 너비우선탐색을 하다가 도착지점에 도착하면.. 2023. 4. 13. [C/C++] 백준 #2146 다리 만들기(DFS, BFS) 이번 문제는 최단거리를 찾는 문제이긴 하지만, 이동하는데 드는 비용이 항상 같기 때문에 너비 우선 탐색을 사용하면 되는 문제입니다. 문제는 아래의 링크입니다. https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 이 문제를 풀 때에는 두 단계를 걸쳐서 풀었습니다. 일단 섬마다 고유한 아이디를 부여하기 위해서 깊이우선탐색(DFS)을 이용해서 고유 아이디를 붙였습니다. 다음으로는 모든 섬에 대해서 다리를 놓기 위한 최단 거리를 구하는 작업을 하였습니다. 이 .. 2023. 4. 10. [C/C++] 백준 #1697 숨바꼭질(너비 우선 탐색) 이번 문제는 너비 우선 탐색을 이용해서 풀었습니다. 너비 우선 탐색(BFS) 아닌 방법으로도 풀 수 있을 듯 합니다만, 당장 좋은 방법은 떠오르지 않습니다. 그래프 탐색 이론을 배울 때, 너비 우선 탐색은 후에 나오는 프림 알고리즘, 다익스트라 알고리즘, A* 알고리즘의 근간이 됩니다. 너비 우선 탐색은 큐(Queue)를 사용하는데, 후에 나오는 알고리즘들은 우선 순위 큐(Priority Queue)를 사용한다는 점이 다릅니다. 사실 간선의 가중치 값이 1인 그래프를 생각한다면, 다익스트라 알고리즘을 사용할 수 있지만, 굳이 그럴 이유가 없는 것이 먼저 방문한 것들이 모두 후에 방문한 것들보다 작거나 같은 노드값을 가지고 있기 때문에 우선순위 큐를 사용할 하등의 이유가 없습니다. 제가 작성한 소스입니다... 2022. 9. 30. 이전 1 2 다음 728x90 반응형
