[ DFS/BFS - 2606 ] 바이러스(C++/BFS)

---

접근법

 

가장 기본적인 BFS/DFS 문제 중 하나이다. 이번 포스팅에서는 BFS에 대하여 알아보고, BFS 방식으로 풀어볼 것이다. 물론, DFS로 풀어도 상관없다.

 

BFS(Breadth First Search)

BFS는 너비 우선 탐색 방법이다. 순서는 다음과 같다.

 

1. 시작 노드 StartNode 방문.

2. 노드 StartNode에 인접한 정점 중 방문하지 않은 정점에 대하여 모두 Queue에 저장

3. Queue에서 정점을 삭제하면서 새로운 StartNode를 설정하고, 단계(1)을 수행

4. Queue가 Empty 상태이면 종료

 

이에 대한 수도코드는 다음과 같다. 

 

수도코드 기반으로 그대로 구현하면 된다. 3번 과정에서 Queue에 저장한 노드들에 대하여 단계 1을 반복하므로 while문으로 반복 중이며, 방문 여부는 visited 배열, 인접 노드는 Graph(2차원 배열)로 관리하면 된다.

 

---

정답

#include<iostream>
#include<queue>
using namespace std;

const int MAX = 101;

queue<int> q;
int32_t ars32_Graph[MAX][MAX] = { 0 };
bool arb_Visited[MAX] = { false };		// visited 배열 초기화
int32_t s32_Result = 0, s32_NodeCnt, s32_EdgeCnt;

void DoBFS(int s32_StartNode);

int main()
{
	int32_t s32_I, s32_J, s32_K, s32_StartNode;

	cin >> s32_NodeCnt >> s32_EdgeCnt;
	for (s32_I = 0; s32_I < s32_EdgeCnt; s32_I++)
	{
		cin >> s32_J >> s32_K;

		// 무향 그래프 -> 대칭
		ars32_Graph[s32_J][s32_K] = 1;
		ars32_Graph[s32_K][s32_J] = 1;
	}

	s32_StartNode = 1;
	DoBFS(s32_StartNode);

	printf("%d\n", s32_Result);

	return 0;
}

void DoBFS(int s32_StartNode)
{
	int32_t s32_Node, s32_I;

	arb_Visited[s32_StartNode] = true;	// 방문 확인
	q.push(s32_StartNode);				// Seed

	// Loop
	while (!q.empty())
	{
		// 하나를 뺀다
		s32_Node = q.front();
		q.pop();

		// Action( 생략 )

		// 다시 집어넣음
		for (s32_I = 1; s32_I <= s32_NodeCnt; s32_I++)
		{
			// 인접 노드 및 방문 확인
			if (arb_Visited[s32_I] == false && ars32_Graph[s32_Node][s32_I] == 1)
			{
				q.push(s32_I);
				arb_Visited[s32_I] = true;
				s32_Result++;
			}
		}

	}

}