BFS의 특징
- 시작 노드에서 가까운 노드를 순서대로 방문
- 완전 탐색
- Queu(First in First out)
- 최단 거리를 구할 때 사용
최대한 적은 node를 들려서 가는 방법
간선의 길이랑 node들이 비례할 때
간선의 가중치에 따라 달라질 수 있다(다익스트라)
구현 순서
1) 그래프 구성
- 각 node간의 관계를 표현한다.
- 구성하는 방법 인접 행렬, 인접 리스트
2) queue 생성
3) 시작 노드 세팅
- queue에 노드 추가
4) queue에서 node(now)를 하나 꺼냄 - 감염 시킬 예정인 node
5) now에서 갈 수 있는 node(next)들 찾기
6) next들을 queue에 추가
7) 4~6단계 반복(더 이상 감염이 안될때까지)(=queue가 비워질때까지)
Danke~😄
