반응형 Bredth First Search4 [C/C++] 백준 #2589 보물섬(너비 우선 탐색) 이번 문제는 너비 우선 탐색을 이용해서 풀었습니다. 플로이드 워샬을 이용해서 풀 수도 있겠지만, 모든 노드가 다 이어진 것이 아니기 때문에 같은 알고리즘 효율이라는 관점에서 너비 우선 탐색을 이용했습니다. https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 문제는 섬안에서 최단거리로 가장 먼 두 점을 찾는 것입니다. 한칸의 거리가 모두 같기 때문에 다익스트라 알고리즘을 사용하지 않고, 너비 우선 탐색을 통해서도 충분합니다. 너비 우선 탐색의 깊이가 가.. 2024. 1. 22. [C/C++] 백준 #2251 물통(너비 우선 탐색) #2251 문제는 고전적인 너비 우선 탐색인데, 노드의 개수가 정확하게 얼마인지 모르는 문제입니다. 하지만 상한은 정해져있습니다. 문제의 링크입니다. https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 이것은 옛날에 퀴즈에 자주 나오는 문제입니다. 3개의 물통을 가지고 정해진 물의 양을 만드는 방법으로 퀴즈를 풀었습니다. 그러한 것을 프로그램으로 푸는 방법입니다. 그림과 같이 용량이 정해져있는 3개의 물통이 있습니다. C에는 물.. 2023. 4. 19. [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. 이전 1 다음 728x90
