BFS ( Breathe First Search )

학교시간에 알고리즘 강의를 수강은 하였으나,,

이런 거에 대해 배운 기억이 없는 학부생으로써 (진짜 안배웠을까..?)

혼자 검색하면서 공부해서 끄적 끄적 남겨보는 자료입니다.

 

BFS, DFS 가 있는데

일단 포스트할 것은 BFS (너비 우선 탐색)인데 꽤나 생소해서 어려웠다고 해야하나.. 암튼 구현하기가 어려웠다.

왜 배운 적 없는 것 같지.. 개인적으로 가지고 있는 알고리즘 책엔 나와있어서 유튜브와 같이 공부해보았다.

 

 

이 알고리즘엔 한 개의 큐가 필요한데,

해당 그래프가 있다고 하고 큐를 한 개 만들어줌.

 

이렇게 만들어진 그래프에서

너비를 중심으로 모든 노드를 탐색해주는 것이다!

 

시작할 노드를 지정해서 그곳부터 큐에 넣어주면 된다.

(0,0) 부터 시작을 하면 Queue에 push를 해준다.

 

그 다음, 큐에서 노드를 POP한 다음 자식 노드들을 Queue에 PUSH 해주고 POP한 노드는 출력하는 방식으로 진행한다.

여기서 한 번 큐에 들어간 자식노드들은 다시 넣지 않는 것이당!

 

(0, 0)을 출력해주었고, 자식 노드인 (1, 0), (0, 1)을 Queue에 PUSH해 넣어준다.

 

그 다음 (1, 0) 노드를 POP해 주었는데 이 노드는 자식노드가 없어서 넘어가고 (0, 1)은 (1, 1)인 자식노드가 있으니까 Queue에 넣어준다.

 

(0, 1) 의 자식노드는 이미 모두 방문하였으므로 꺼낸다.

 

 

 

(1, 1)을 꺼내고 자식노드들을 큐에 넣어준다.

 

(0, 2)를 꺼내고 자식노드인 (0, 3)을 큐에 넣어준다.

 

(1, 2) 를 꺼내고 자식노드인 (1, 3)을 큐에 넣어준다.

 

큐에서 꺼내준다.

 

큐에서 꺼내준다.

 

이런식으로 진행이 되는 것 같다.

 

정리를 하면,

1. 시작할 노드를 정하여, 큐에 넣어준다.

2. 큐에 들어간 노드를 꺼내고, 그들의 자식노드들을 큐에 넣어준다.

3. 이미 꺼낸 노드들은 다시 큐에 넣지 않는다. (2번을 반복한다.)

 

 

BFS 관련 응용된 자료는 해놓았다.

https://geol2.tistory.com/227

1926번. 그림