BFS와 큐

알고리즘 문제를 풀면 BFS문제가 많이 출제가 되는 것을 알 수 있다.
BFS의 사전적 정의를 생각해보면 Breadth-First Search 너비 우선 검색으로 너비를 우선적으로 검색하는 알고리즘이다.

너비를 구한다는 것이 무슨 말일까?
간단히 생각해서 범위를 확장을 시킨다는 의미다. 
확장을 시키려면 어떻게 하는것이 가장 효율적일까?
이것도 생각할 문제이긴 하지만 일반적으로 가장 효율적인 방식은 바이러스 처럼 점염을 시키는 것이 가장 빠를 것이다. 
최근에 발생한 바이러스는 코로나바이러스다. 
코로나 바이러스의 감염 방식은 여러가지가 있지만, 내가 생각할때 코로나 바이러스가 빠르게 확산을 시킬 수 있었던건 근처에 있는
사람에게 공기중으로 감염이 된것이 빠르게 확산을 시킨 이유가 아닐까 싶다.
이걸 다른 말로 인접한 사람에게 감염을 시켰다고 말할 수 있다.
이게 BFS의 방식이다. 이 방식이 근처의 공간에게 영향을 주면서 가장 빠른 방법이기 때문이다.
추후에 BFS와 DFS의 차이점에대해 심도있는 고민을 해보겠지만 지금은 주제가 주제인 만큼 넘어가도록 하겠다.

BFS가 너비를 이용해서 구한다는거 알겠는데 왜 하필 사용하는 자료구조가 큐일까?
이건 단순히 생각해서 가장 효율적이기 때문이다. 왜 효율적인지 생각해봐야한다. 
큐는 선입선출의 방식으로 먼저 큐에 넣으면 그것이 가장 먼저 빠지는 자료구조이다.
이게 핵심이다.
물론 킹갓제너럴 리스트로 BFS를 구현할 수 있다. 근데 왜 리스트로 사용하지 않고 큐를 사용하는 걸까?
리스트도 선입선출을 사용할 수 있는데 말이다. 그건 바로 큐는 선입선출이 디폴트인것에 반해 리스트는 억지로 그 행위를 해야 하기 때문일거라 생각한다.

큐는 요소를 뽑아내는 순간 가장 먼저들어온거로 인식이 되지만
리스트는 첫번째꺼로 조회를 하고 뽑아내야 하기 때문에 2가지 과정이 필요하기 때문에 큐를 사용하는것이 더 효율적이다.

그러면 다시 돌아와서 BFS와 큐는 어떤 영향관계이기에 BFS는 큐를 사용하는 걸까?

Queue<Point> q = new LinkedList<>();
q.add(new Point(0, 0));
while (!q.isEmpty()) {
var point = q.poll();
int cx = point.x;
int cy = point.y;
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
q.add(new Point(nx, ny));
}
}

이게 BFS의 방식이다. 
참고로 dx,dy에는 좌표값이 들어가 있다.
Point에는 x와 y가 들어간 클래스이다.

암튼 저기서 가장 중요한 부분은

for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];  // {0,0,1,-1}
int ny = cy + dy[i];  // {1,-1,0,0}
q.add(new Point(nx, ny));
}

요 부분이라 생각이 드는데
이 코드는 인접한 요소를 큐에 넣는 작업을 하고 있다.
그리고 위에서 지속적으로 큐에서 뽑아내고 있는것을 확인 할 수 있다.
이말이 무슨 말이냐면 자기자신을 기준으로 상하좌우를 큐에 넣는다는거다. 

코드 정황상 뜬금없이 0,0넣었는데 그 다음에 10,10이 들어가지는 않을거다.
0,0을 넣는다면 1,0 또는 0,1이 들어가진다.
그럼 자연스럽게 색이 칠해지고 
0,0일때 1개만 방문했던게 그 다음에는 3개가 방문으로 한것으로 바뀌어지고
이것을 계속 하면 1 -> 3 -> 5 -> 7 ... 이런식으러 점점 확장되어진다는 것을 알 수 있다.

솔직히 아직 완벽하게 설명이 안된거 같긴한데 나는 이정도가 한계인거 같다.
암튼 큐의 이러한 성절때문에 bfs를 이용하는게 아닐까 싶다....