반응형 BFS6 [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. #1405 미친 로봇(Full Search, Back Tracking) 이번 문제는 경로를 다니면서, 지나온 길을 거치지 않을 확률을 계산하는 것입니다. 난이도 Gold V로 어렵지는 않은 문제이고요. 복잡한 알고리즘이 아니라, 단순한 백트랙킹을 구현하면 됩니다. 동서남북으로 움직일 수 있는 확률이 주어지고, 동서남북으로 확률적으로 N칸 움직였을 때, 지나온 경로를 다시 방문하지 않는 경로로 움직일 확률이 얼마일까를 계산하는 문제입니다. 예를 들어서 로봇이 NESW로 순차적으로 움직였다면, 원위치로 돌아왔으니, 지나온 경로를 지나게 됩니다. NNES 라던지, SWWS 와 같은 경로는 4칸을 움직이면서 지나온 경로를 지나지 않는 움직임이 됩니다. 문제를 풀기 위해서는 BFS, DFS 들 중 어떤 것을 사용하든 상관이 없습니다. 전 편한 DFS를 사용했습니다. 최대 움직임은 1.. 2020. 2. 23. 이전 1 다음 728x90
