🖤알고리즘 이론 - BFS에 대하여 JAVA

목차
1. BFS란?
    (1) 그래프에 대한 기본 설명
    (2) 그래서 BFS라는 게 뭔데? 
    (3) BFS의 원리 설명 (그림 예시를 들며)

1. BFS란?

BFS란 Breadth First Search의 약자로, 넓이 우선 탐색을 의미한다. 

"넓이 우선 탐색이 뭐시여?"

BFS는 그래프로 표현이 가능한 환경에서 사용하는 알고리즘이다. 따라서 BFS에 대하여 이해하려면 그래프를 이해 해야한다. 그래프는 다음에 더 자세히 설명하고, 지금은 BFS 설명에 필요한 정도만 알아보도록 하자.

 

(1) 그래프에 대한 기본 설명  

양방향 그래프와 단방향 그래프

먼저 그래프의 구성요소에 대해 알아보자면, 숫자가 적혀있는 거점을 노드, 선을 간선이라고 한다.

또한 양방향 그래프는 간선에 방향이 없어 A -> B가 가능하면 B -> A로 가는 것도 가능한 그래프를 의미한다.

반면에 단방향 그래프는 보는 그림에서와 같이 1 -> 3은 가능하지만 3 -> 1로의 이동은 불가능한 그래프를 의미한다. 
'인접하다.'의 의미는 '노드와 노드가 간선 한 개로 이어져 있다.' 를 의미한다.

 

(2) 그래서 BFS라는 게 뭔데? 

 BFS란 그래프에서 자신과 인접한 노드부터 우선적으로 확인하여 일처리를 하는 알고리즘을 뜻한다.

a. 준비 사항

- queue, 방문배열, 해당 문제에서 처리하라는 내용에 대한 로직 

BFS 알고리즘은 Java에서는 queue를 가지고 구현한다. queue는 선입 선출의 구조이기 때문에, 출발점에서 인접한 노드부터 순차적으로 나오면, 출발점에서 가까운 순으로 순차적으로 일 처리를 할 수 있기 때문이다. 
  또한 방문 배열이 필요하다. 검은뱀과 흰뱀이 서로의 꼬리를 물고 있는 형태를 중국에서는 태극이라고 했다. 양방향이든 단방향이든, 그래프에서는 이런 태극과 같은 순환 구조가 생길 수 있다. (A->B, B->C, C->A) 이때 방문한 노드를 미리 체크 안해두면, 우리의 로직은 같은 노드를 무한히 반복하며 돌 것이다. 따라서 방문 배열이 필수적이다. 

 

b. 원리 

- 1. 출발 노드를 방문처리하고 queue에 넣는다. 

- 2. queue가 빌 때까지 3,4번을 반복한다.

- 3. queue의 front 부분에서 값을 하나 꺼낸다. (이때 뭔가 처리해야할 일이 있으면 처리한다.)

- 4. 꺼낸 값의 인접한 노드들 중 방문하지 않은 노드가 있다면, 방문처리하고 queue에 넣는다.

 

c. 주의사항

- 방문 배열은 방문 예정인 값을 나타낸다. 

뭔 소리야? 

queue에 값이 들어가는 순간, 방문이 확정적이다. 따라서 방문한 것이나 다름 없다. 
따라서 queue에 들어가기 전에 방문 배열에 방문 했다고 표시한다. 

이렇게 하는 이유는, 

(3) BFS의 원리 설명(그림 예시를 들며)

① 시작점이 1번이라면 먼저 1번을 deque에 넣는다. 

② 1을 poll 한다. 이때 1의 인접한 노드인 2,3을 deque에 넣는다.

③ 2번을 poll한다. 2번에 인접한 5,6번 노드를 넣느다. 

④ 3번을 poll한다. 5번은 방문했음으로  재방문은 하지 않고, 4번을 방문한다.

⑤ 이제 더 이상 방문할 노드가 남지 않았음으로 BFS를 종료한다.