반응형 너비 우선 탐색6 [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++] 백준 #1743 음식물 피하기(너비우선탐색) 이번 문제는 섬의 개수 구하기라든지, 섬의 넓이 구하기 문제와 비슷한 유형으로 너비 우선 탐색(BFS)나 깊이 우선 탐색(DFS)를 이용해서 푸시면 됩니다. 구현 자체는 깊이 우선 탐색이 더 쉽습니다. 너비 우선 탐색은 일단 큐를 사용해야 하기때문에 구현이 조금 더 까다롭다고 볼 수 있습니다. 그에 비해서 깊이 우선 탐색을 이용하면 재귀함수만 이용하면 되죠. 구현도 훨씬 간단하고요. 제가 작성한 소스입니다. 소스는 참고로 봐주세요. //-------------------------------------------------------------------- // baekjoon #1743 - Avoid The Lakes // - by Aubrey Choi // - created at 2019-08-06 .. 2022. 10. 6. [C/C++] 백준 #1726 로봇(너비우선 탐색) 이번 문제는 복잡해 보이기는 하지만, 의미를 되새겨보면 마이크로 마우스 등에서도 사용할 수 있습니다. 실제 마이크로 마우스에서도 직진하는 경우에는 속도가 빠르기 때문에, 비슷하게 로직을 작성할 수가 있습니다. 문제는 로봇이 있는데, 현재 바라보는 방향이라면 최대 3칸까지 직진하는 명령을 줄 수 있습니다. 회전을 하는 것도 역시 명령을 줄 수 있는데, 이 때, 반시계 방향 또는 시계방향으로 90도 회전하라고 할 수 있습니다. 로봇이 움직일 공간 정보와 시작지점과 끝지점이 주어지면, 시작지점에서 끝지점까지 최소한의 명령어로 움직이게 하고싶습니다. 로봇은 동서남북 4방향으로만 바라볼 수 있고, 격자형태로 공간은 주어진다고 합니다. 아래 그림과 같이 로봇이 다닐 수 있는 길은 0의 값으로, 로봇이 갈 수 없는 .. 2022. 10. 6. [C/C++] 백준 #1697 숨바꼭질(너비 우선 탐색) 이번 문제는 너비 우선 탐색을 이용해서 풀었습니다. 너비 우선 탐색(BFS) 아닌 방법으로도 풀 수 있을 듯 합니다만, 당장 좋은 방법은 떠오르지 않습니다. 그래프 탐색 이론을 배울 때, 너비 우선 탐색은 후에 나오는 프림 알고리즘, 다익스트라 알고리즘, A* 알고리즘의 근간이 됩니다. 너비 우선 탐색은 큐(Queue)를 사용하는데, 후에 나오는 알고리즘들은 우선 순위 큐(Priority Queue)를 사용한다는 점이 다릅니다. 사실 간선의 가중치 값이 1인 그래프를 생각한다면, 다익스트라 알고리즘을 사용할 수 있지만, 굳이 그럴 이유가 없는 것이 먼저 방문한 것들이 모두 후에 방문한 것들보다 작거나 같은 노드값을 가지고 있기 때문에 우선순위 큐를 사용할 하등의 이유가 없습니다. 제가 작성한 소스입니다... 2022. 9. 30. [C/C++] 백준 #1600 말이 되고픈 원숭이(너비 우선 탐색) 이번 문제는 너비 우선 탐색으로 풀었습니다. 그래프 이론 중에 프림 알고리즘, 다익스트라 알고리즘, 그리고 A* 알고리즘 모두 너비 우선 탐색(Bredth First Search)이 기초가 됩니다. 이 문제에서 너비 우선 탐색을 쓴 이유는 노드간의 간선의 값이 1이기 때문입니다. https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 그렇지만, 말(knight)의 이동이 k번으로 제한된다는 것때문에 별도의 자료를 사용해야 합니다. 일단.. 2022. 9. 11. 이전 1 다음 728x90
