<aside> 🔍 오늘은 BFS(Breadth First Search)에 대해 알아보자. 긴 서론 필요없이 바로 출발해 보자.

</aside>

최근에 실연을 겪은 한 요리사 친구가 있다. 이 친구는 너무나도 연인과 만나고 싶어 연락을 시도했지만, 끝끝내 연락이 닿지 않았다. 그러다 이 요리사 친구가 기가 막힌 생각을 하나 해 냈다. 바로 연인을 자신의 식당으로 반드시 오게끔 만드는 방법이다.

우선 가장 가까운 지인 한 사람을 붙잡아 음식점 줄에 세운다. 그리고 다음을 반복하겠다고 한다.

1. 줄 맨 앞의 사람을 음식점 안으로 들여보낸다.
2. 만약 그 사람이 그녀라면, 이 반복을 멈춘다.
3. 그 사람의 친구들 중 음식점에 와보지 않은 친구들을 불러 줄에 세운다.

줄이 사라질 때까지 이 과정을 반복하면 이 세상 모든 사람들을 다 데려올 수 있을 것 같다. 결국 이러한 방법을 써서 그 요리사는 그녀를 찾을 수 있었다고 하는 해피엔딩 스토리가 되겠다.

물론 이 스토리는 믿거나 말거나고, 그게 중요한게 아니라 이 방법을 알아두면 어딘가 유용하게 사용하지 않겠는가! 우리 프로그래머들은 곧장 코드로 정리해 보자.

// 줄을 만들고 가장 가까운 지인(root)을 줄에 세워 보자.
std::queue<human> q;
q.push(root);

// 줄이 사라질 때까지 다음을 반복하자.
while (!q.empty()) {
		// 1. 줄의 맨 앞 사람을 음식점 안으로 들여보낸다.
		auto person = q.front();
		
		// 2. 그 사람이 그녀라면, 반복을 멈춘다.
		if (person == her) return person;
		q.pop();

		// 3. 그 사람의 친구들 중, 음식점에 와보지 않은 사람을 데려와 줄에 세운다.
		for (const auto &friend : person.friends()) {
				if (!person.has_visited) q.push(friend);
		}
}