# BFS
로직은 아래와 같습니다.
* 동영상에서 보이듯 시작 노드를 방문하고 해당 노드에 연결되어 있는 노드들을 전부 방문합니다.
* 다음으로 그 노드들에서 위 BFS를 다시 진행합니다.
구현은 **큐**를 사용합니다. 아래는 위 그래프에서 큐에 들어가고 나가는 요소들의 모습입니다.\
먼저 루트 노드인 0이 들어갔다 나오면서 0과 연결된 1과 2를 append시킵니다. \
이후 노드1을 popleft 시키면서 1과 연결된 3,4,5 노드를 append시킵니다. \
다음으로 popleft되는 것은 노드2일 것입니다. \
선입선출이라는 특징으로 인해 bfs는 큐로 구현할 때 강력할 수밖에 없겠죠?
다만 BFS를 수행할 때 꺼냈던 노드를 또 다시 방문하는 상황이 발생할 수 있습니다. \
이렇게 되면 갔던 노드를 또 다시 가게 되어 무한 반복의 늪에 빠지게 됩니다.\
따라서 visited 배열을 이용해 방문 여부를 체크해 한 번 갔던 노드는 다시 방문하지 않도록 하는 것이 핵심입니다.
아래 코드를 참고해 그래프를 직접 그려가며 BFS 시 visit 여부 체크 시점을 언제로 지정하면 좋을지 생각해봅시다 !
```python
from collections import deque
def bfs(graph, start, visited):
queue=deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
graph = [
[1,2], #0번 노드에서 1과 2로 이동 가능하다.
[3, 4, 5], #1번 노드에서 2,3,8로 이동 가능하다.
[6,7], #2번 노드에서 1,7로 이동 가능하다.
[8],
[3],
[],
[],
[],
[]
]
visited = [False] * 9
bfs(graph, 0, visited) #출력 : 0 1 2 3 4 5 6 7 8
```
{% embed url="" %}
2644번에서는, BFS로 그래프를 탐색하며 현재 탐색하는 노드A에서 갈 수 있는 노드B에 현재 노드 값(A)의 +1을 합니다. \
그리고 또 다시 노드B로 이동합니다.
이런 식으로 모든 노드들을 BFS로 탐색을 마치친 후, 찾고자 하는 노드의 인덱스의 값을 출력해주면 됩니다.
```python
from collections import deque
def bfs(node):
queue = deque()
queue.append(node)
while queue:
node = queue.popleft()
for n in graph[node]:
if check[n] == 0:
check[n] = check[node]+1
queue.append(n)
n = int(input())
graph = [[] for _ in range(n+1)]
s, e = map(int, input().split())
for _ in range(int(input())):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
check = [0]*(n+1)
bfs(s)
print(check[e] if check[e] > 0 else -1)
```
기본 알고리즘 시간에 배웠던 floodfill도 기본적으로 bfs 로직입니다.\
floodfill의 경우 direction 방향을 선택하여 상하좌우부터 탐색하는 bfs 로직이라고 보시면 됩니다.
```python
direction = [(0,1),(1,0),(-1,0),(0,-1)]
```
## 풀어볼 문제
{% embed url="" %}
{% embed url="" %}
{% embed url="" %}
