[바킹독: 알고리즘] BFS 알고리즘 (너비 우선 탐색)

※ (링크) 바킹독 유튜브 영상을 통해

학습한 내용을 정리한 것입니다.

 

본인은 JAVA를 활용해 학습하였습니다

비상업적 목적이며, 개인 복습을 위해 업로드한 글임을 다시 한 번 더 이야기드립니다.

 

본문의 모든 내용의 출처는 아래 명시된 링크와 같습니다.

 

 

[목차] 알고리즘 설명, 예시, 응용1 - 거리 측정, 응용 2- 시작점이 여러 개 일 때, 응용3 - 시작점이 두 종류일 때, 응용4 - 1차원에서의 BFS

[실전 알고리즘] 0x09강 - BFS

출처: blog.encrypted.gg/941?category=773649

---

알고리즘 설명

BFS는 Breadth First Search로 다차원 배열에서 각 칸을 방문할 때, 너비를 우선으로 방문하는 알고리즘 입니다. 원래 BFS는 그래프라는 자료구조에서 모든 노드를 방문하기 위한 알고리즘입니다. 여기서 이야기하는 그래프는 우리가 알고 있는 주식 차트와 같은 것이 아니라, 정점과 간선으로 이루어진 네트워크망 형태로 되어있는 자료구조를 이야기합니다.

 

그렇기에 BFS를 이해하려면, 그래프 자료구조에 대한 이해가 선행되어야 하는 것이 좋습니다. 

 

---

예시

(0, 0)과 파란색으로 이어진 크기를 판단하는 예시를 한다고 해보겠습니다.

 

출처: https://blog.encrypted.gg/941?category=773649

 

1. 초기 셋팅
   BFS는 좌표를 담을 큐가 필요합니다. BFS알고리즘이 시작되면, (0, 0)에 방문했다는 표시를 남기며 해당 좌표를 큐에 넣습니다.
   
   
2. 이후 큐가 빌 때까지, 큐의 front를 빼고 해당 좌표의 상하좌우를 살펴보며 큐에 넣는 작업을 반복합니다.
   
   
3. 이때 좌표의 이동은 큐의 front 좌표를 기준으로 상하좌우에 인접하며, 아직 방문하지 않은 파랑칸을 만족해야 합니다.

[1번 실행] (0, 0)

2번으로 맨 앞에 있던 (0, 0)은 빠져나갑니다.

(0, 1)

(1, 0)

2번과 3번을 반복합니다.

2번의 실행으로 맨 앞에 있던 (0, 1)은 빠져나갑니다. 그리고 빠져나간 (0, 1)의 상하좌우칸을 확인해 파랑칸을 만족하는 경우 해당 좌표를 큐에 넣습니다. (1, 1)은 조건에 만족하지 않기에 입력하지 않으며, (0, 2)는 방문하지 않은 파랑칸으로 큐에 입력합니다.

(1, 0)

(0, 2)

2번과 3번을 반복합니다.

2번의 실행으로 맨 앞에 있던 (1, 0)은 빠져나갑니다. 그리고 빠져나간 (1, 0)의 상하좌우칸을 확인해 파랑칸을 만족하는 경우 해당 좌표를 큐에 넣습니다.

(0, 2)

(2, 0)

(0, 2)를 pop하여, 상하좌우를 살핍니다.

(2, 0)

(2, 0)을 pop하여, 상하좌우를 살핍니다.

(3, 0)

(2, 1)

(3, 0)을 pop하여, 상하좌우를 살핍니다.

(2, 1)

(3, 1)

(2, 1)을 pop하여, 상하좌우를 살핍니다.

(3, 1)

(2, 2)

(3, 1)을 pop하여, 상하좌우를 살핍니다.

(2, 2)

(4, 1)

(2, 2)를 pop하여, 상하좌우를 살핍니다.

(4, 1)

(4, 1)을 pop하여, 상하좌우를 살핍니다.

 

다시 정리하겠습니다.

 

• 시작 칸을 큐에 넣고 방문한 표시를 남깁니다.
  
  
• 큐에서 원소를 꺼내 그 칸에 상하좌우로 인접한 캄에 대해 3번을 진행합니다.
  
  
• 해당 칸을 이전에 방문했다면 아무 것도 하지 않으며, 처음으로 방문했다면 방문한 표시를 남기고 해당 칸에 큐를 삽입합니다.
  
  
• 큐가 빌 때까지 2번을 반복합니다.

모든 칸이 큐에 한 번씩 들어가므로, 시간복잡도는 칸이 N개 일 때, O(N)입니다.

BFS는 정석적인 코드가 존재하며, 해당 코드는 아래와 같습니다. 즉, 기본 틀이며 이해하고 숙지해두는 것이 굉장히 중요합니다. (추가. 삼성 A형을 풀기 위해서는 BFS가 정말 중요합니다. )

 

 

BFS 코드를 작성할 때, 절대 실수하면 안 되나 자주 하는 실수들을 정리해보겠습니다.

 

• 시작점에 방문 표시를 남기지 않습니다.
  이 경우 시작점을 두 번 방문할 가능성이 높습니다.
  
  
• 큐에 넣지 않고 방문한 표시를 남기지 않고, 큐에서 빼낼 때 방문했다는 표시를 남깁니다.
  이 경우 같은 칸이 큐에 여러번 들어가게 되어 시간초과나 메모리 초과가 발생할 수 있습니다.
  
  
• 이웃한 원소가 범위를 벗어났는지 체크를 잘못하는 경우입니다.
  
  

---

예시

(1) BOJ 1926번 그림

 

1926번: 그림

github.com/Jeong-sky-1003/DataStructure/blob/main/src/barkingdog/chap09/BOJ1926.java

Jeong-sky-1003/DataStructure

소요 시간: 42분 30초

---

응용 1 - 거리 측정

BOJ 2178번: 미로 탐색

2178번: 미로 탐색

github.com/Jeong-sky-1003/DataStructure/blob/main/src/barkingdog/chap09/BOJ2178.java

Jeong-sky-1003/DataStructure

소요 시간: 21분 49초

---

응용 2 - 시작점이 여러 개 일 때

BOJ 7576번: 토마토

7576번: 토마토

github.com/Jeong-sky-1003/DataStructure/blob/main/src/barkingdog/chap09/BOJ7576.java

Jeong-sky-1003/DataStructure

소요 시간: 44분 24초

---

응용 3 - 시작점이 두 종류 일 때

BOJ 4179번: 불!

4179번: 불!

github.com/Jeong-sky-1003/DataStructure/blob/main/src/barkingdog/chap09/BOJ4179.java

Jeong-sky-1003/DataStructure

[ ㅠㅠ 이 문제는 다른 사람 풀이를 보고 결국 풀었다.. 쉽지 않네.. ]

첫 풀이 당시 불과 지훈이의 이동 조건을 [ !que.isEmpty() ] 일 경우로 진행했으나, 시간 흐름에 따라 동시에 움직인다는 현실이 반영되지 않았음이로 결과에 오류가 발생하였습니다.

각 que의 size로 이동을 제어한 결과 동시간에 움직이는 효과를 낼 수 있었습니다.
이전 풀이에서 간과했던 것은 지훈이가 있던 자리에 불이 갈 수 있는 것인데, 해당 조건이 적용되지 않았었으며, 앞서 이야기하였듯 동시에 움직인다는 조건도 적용되지 않습니다.

지훈이는 무조건 0인 길만 움직일 수 있고, 불은 벽과 불이 지나온 길을 돌아갈 수 없습니다.
이를 미로 생성에 반영해 숫자로 제어하여 해결할 수 있었던 것입니다.물론 시간초는 꽤 나왔지만 ㅠㅠ

 

시작점이 여러 개인 경우 문제를 풀 경우 생각할 점이 추가로 존재합니다. 만약 A와 B 두 개의 시작점이 존재하며, 서로의 시작점이 영향을 준다고 해보겠습니다. 즉, 물과 불이 동시에 퍼져 만나면 상호작용한다고 가정을 해보겠습니다. 이를 생각하면 어느 하나를 끝까지 전파시키는 것이 불가합니다. [ BOJ 18809번 문제 ]

 

이러한 문제는 백트래킹 기법을 알고 있어야 해결이 가능합니다. 이런 상황에서는 시간 순으로 A와 B를 동시에 진행시켜야만 합니다.

---

응용 4 -  1차원에서의 BFS

BOJ 1697번: 숨바꼭질

1697번: 숨바꼭질

github.com/Jeong-sky-1003/DataStructure/blob/main/src/barkingdog/chap09/BOJ1697.java

Jeong-sky-1003/DataStructure

이 문제 또한 풀이 시간을 한 시간을 넘겼음에도 불구하고 스스로 풀지 못했습니다..ㅠㅠ 문제 풀이 개선점!

입력될 수 있는 값과 해당 값으로 연산할 때의 최댓값을 잘 인지하고 배열의 범위를 선언하는게 좋을듯 합니다. 또한 이런 1차원 BFS의 경우 que와 poll( )로만 진행하는 데에 메모리초과가 발생하는 경우가 많았습니다. 즉, 불필요한 연산 또한 엄청 많았죠 ㅠㅠ

이런 문제의 경우 2차원 배열을 사용해 BFS를 풀었던 것처럼 1차원 배열을 이용해 문제를 풀 수 있습니다. 이때 앞서 이야기했듯 입력되는 값의 최솟값과 최댓값, 그리고 연산되는 값이 어떻게 되는지 파악하는 습관을 꼭! 키우는 것이 좋을듯 합니다.

추가로 메모하자면, 배열의 크기를 처음에 n과 k중 최댓값으로 하였는데요. 이로 NullPointException이 발생했습니다. 어찌되었건 값의 연산이 발생하면서 해당 배열이 존재하지 않아 발생한 예외로 인식되네요.

아무튼 최솟값과 최댓값을 꼭 잘 살핍시다!

---

문제집

github.com/encrypted-def/basic-algo-lecture/blob/master/workbook.md

encrypted-def/basic-algo-lecture

www.acmicpc.net/workbook/view/7313

문제집: 0x09강 - BFS (BaaaaaaaaaaarkingDog)