[알고리즘] BFS 문제 유형 분석 및 풀이법

요즘 풀이는 자주 올리지 않지만 백준을 많이 풀고 있는데 많이 출제하고 많이들 푸는 BFS 문제의 유형이 어느 정도 나뉘어져 있는 것 같아서 각 유형별 풀이법을 정리해 보고자 한다

1. 최단 거리 구하기

사실 BFS를 사용하는 가장 중요한 문제라고 생각하면 좋다. 원래 BFS의 특징상 특정 정점 사이의 최단거리를 구하기에 최적화 되어있는데, 너무 기본적이라 자주 출제되는 유형의 문제도 아니고 문제 자체도 별로 많은 것 같지는 않다.

풀이법은 시작 정점에서부터 모든 정점에 대해 BFS를 돌린 후 거리를 저장해 두면 된다. 그렇게 하면 어느 정점이든 도착 정점이 되더라도 거리를 알 수 있다.

예제 문제 🔗

• 백준 2178번 미로탐색 (실버 1)
  • 링크 : https://www.acmicpc.net/problem/2178

2. 영역 구하기

그리드 안의 영역이 주어지고, 각 영역의 개수나 최대 넓이 등을 구하는 문제이다.

풀이법은 모든 그리드 안의 칸에 대해 반복문을 돌면서 BFS의 시작점이 될 수 있는 곳을 찾고, BFS를 돌린 후 방문한 영역을 표시 해놓으면 된다. BFS를 돌릴 때마다 개수를 count하거나 BFS를 돌리면서 넓이를 체크하면 영역의 개수와 최대 넓이를 구할 수 있다.

예제 문제 🔗

• 백준 1926번 그림 (실버 1)
  • 링크 : https://www.acmicpc.net/problem/1926
• 백준 1012번 유기농 배추 (실버 2)
  • 링크 : https://www.acmicpc.net/problem/1012
• 백준 10026번 적록색약 (골드 5)
  • 링크 : https://www.acmicpc.net/problem/10026

3. 시작점이 여러 개인 BFS

시작점이 여러 개이면 각각의 시작점에 대해 BFS를 한번씩 다 돌릴 수도 있지만 시작점이 많을 경우 시간 내로 문제가 해결되지 않을 수 있다.

풀이법은 모든 시작점을 큐에 미리 넣어놓고 BFS를 돌면 된다. 시작점은 입력 받을 때나 반복문으로 체크해서 즉시 큐에 넣으면 되기 때문에 그리 어렵지는 않다.

예제 문제 🔗

• 백준 7576번 토마토 (골드 5)
  • 링크 : https://www.acmicpc.net/problem/7576
• 백준 7569번 토마토 (골드 5)
  • 링크 : https://www.acmicpc.net/problem/7569

4. 시작점이 여러 종류인 BFS

시작점이 여러 개인 것과 달리 다른 종류인 것이다. 시작점이 여러 개인 것은 어디에서 시작하더라도 같은 결과를 내지만 시작점이 여러 종류인 것은 각각에 대해 BFS를 따로 돌려야 하고 결과도 다르다.

풀이법은 먼저 하나의 시작점에 대한 BFS를 돌려 미리 각 칸에 대한 거리 등을 체크 해놓고, 다음 다른 시작점에 대해 BFS를 돌리며 처음 돌렸던 BFS 결과와 비교하는 것이다. 대신 서로의 시작점이 독립적일 경우에만 가능하다. 서로 BFS를 돌리며 영향을 준다면 백트래킹을 추가로 이용해서 문제를 풀어야 한다.

예제 문제 🔗

• 백준 4179번 불! (골드 4)
  • 링크 : https://www.acmicpc.net/problem/4179
• 백준 5427번 불 (골드 4)
  • 링크 : https://www.acmicpc.net/problem/7569

5. 거리 탐색

앞에서의 문제들은 그리드로 이루어진 영역 안에서 한 칸씩 탐색하는 경우가 많았는데, 이번에는 정해진 거리를 이동하며 탐색하는 문제이다. 이 문제도 어렵지는 않다.

풀이법은 간단하다. 원래 상하좌우로 탐색하도록 하던 거리 벡터를 문제에서 주어진 거리 범위에서 이동하도록 설정해주고 해당 거리에 따라 BFS를 돌리면 된다.

예제 문제 🔗

• 백준 1697번 숨바꼭질 (실버 1)
  • 링크 : https://www.acmicpc.net/problem/1697
• 백준 7562번 나이트의 이동 (실버 1)
  • 링크 : https://www.acmicpc.net/problem/7562