기록보관소

바이러스 문제는 BFS를 이용하는 전형적인 문제이다. BFS의 특성인 "연결된 모든 노드를 찾는다"를 이용하여 1번 컴퓨터에서 출발하여 도달할 수 있는 모든 컴퓨터의 개수를 찾아야 한다. 이러한 특성을 이용한 기법을 "Flood Fill"이라고 한다. 보통 군집의 개수나 크기를 계산할 때 많이 사용한다. BFS 코드의 템플릿은 다음의 글에서 참고할 수 있다. 해당 템플릿을 변형하면 많은 BFS 문제를 큰 고민없이 빠르게 해결할 수 있다. 2021.09.07 - [알고리즘/문제풀이] - [알고리즘/문제풀이][BOJ 1260번] DFS와 BFS [알고리즘/문제풀이][BOJ 1260번] DFS와 BFS DFS와 BFS는 DFS와 BFS에 대한 가장 기초적이면서도 중요한 문제입니다. DFS와 BFS에 대한 충실..

DFS와 BFS는 DFS와 BFS에 대한 가장 기초적이면서도 중요한 문제입니다. DFS와 BFS에 대한 충실한 이해가 필요합니다. DFS의 경우 처음 발견된 노드를 기준으로 그 노드에 연결된 노드들을 탐색(DFS)를 하는 알고리즘입니다. 여기서 눈치챌 수 있듯이 DFS는 재귀함수로 구현할 수 있습니다. BFS는 너비우선탐색이라는 이름에서 알 수 있듯이 루트 노드를 기준으로 방사형으로 탐색하는 알고리즘입니다. 즉, 루트 노드에서 거리가 1인 노드들을 전부 탐색한 다음 거리가 2인 노드를 탐색하는 방식으로 탐색이 진행됩니다. 이러한 방식으로 탐색하기 위해 BFS는 '큐'라는 자료구조를 활용하여 구현할 수 있습니다. 큐, DFS, BFS에 대한 설명은 다음과 같습니다. 2021.07.07 - [알고리즘/이론]..

BFS는 간단한 검색 알고리즘으로 많은 그래프 알고리즘의 원형이 되는 알고리즘이다. 발견된 정점과 발견되지 않은 정점 사이의 경계선을 균일하게 확장시켜나간다는 사실에서 너비 우선 검색이라는 이름이 유래하게 되었다. 즉, 거리가 k인 정점을 모두 탐색한 후에 k+1의 거리를 갖는 정점을 탐색한다는 뜻이기도 한다. 특징적인 부분으로 이 알고리즘은 그래프 내의 하나의 출발점에서 도달이 가능한 모든 정점을 체계적으로 검색하는 알고리즘이다. (검색이란 그래프 내의 정점을 방문하기 위해 간선을 규칙에 맞춰 따라가는 행위이다.) 또한, 출발점에서 도달이 가능한 모든 정점을 포함하는 너비 우선 트리를 만들며, 이때 각 정점까지의 단순 경로는 출발점에서 특정 정점까지의 거리를 의미한다. (거리란 정점과 정점 사이의 최소..