너비 우선 탐색(BFS)9 [Baekjoon] 16236번: 아기 상어 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 해결 과정 착안 문제에서 아기 상어가 물고기를 먹기 위해 이동하는 최소 경로가 크기에 따라 달라지는 상황에서, 아기 상어가 먹이를 찾아 탐색하는 과정을 구현하는 문제이다. 문제를 처음 접했을 때, 아기 상어의 1 초당 이동 반경을 중심으로 전방향으로 탐색을 하는 방법을 생각해보았다. 즉, 너비 우선 탐색(breadth-first search, BFS)의 원리에 기반하여 주어진 공간 내.. 2023. 5. 30. [Baekjoon] 1260번: DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 해결 과정 착안 문제에서 주어지는 간선 정보를 바탕으로 깊이 우선 탐색(depth-first search, DFS)과 너비 우선 탐색(breadth-first search, BFS) 알고리즘을 구현하는 것을 요구하는 문제이므로, 두 알고리즘의 특징에 유의하여 구현하고자 하였다. 깊이 우선 탐색 알고리즘은 스택(stack) 자료 구조를 활용하여 구현(또는 .. 2023. 5. 8. [Baekjoon] 24444번: 알고리즘 수업 - 너비 우선 탐색 1 https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 문제 해결 과정 착안 간선(edge)의 가중치가 모두 일정한 무향(undirected) 그래프(graph) 자료 구조에서의 너비 우선 탐색 알고리즘(breadth-first search, BFS)을 구현하는 문제이므로, 간단한 그래프 클래스와 문제에서 요구하는 너비 우선 탐색 알고리즘을 구현하였다. 이번에도 한 정점에 대한.. 2023. 5. 7. 이전 1 2 다음
