[백준] 2606 - 바이러스

www.acmicpc.net/problem/2606

2606번: 바이러스

• 한국정보올림피아드 지역본선 2004 초등부 문제
• 단계별로 풀어보기
• 대학교때 코딩 배운 나와 달리 초등부 문제가 DFS 탐색을 이용하는 것은 조금 신기하긴 했다.

---

• 풀이
  • 1260 - DFS와 BFS에서 인접행렬을 사용한 DFS를 std::vector<>를 이용한 인접리스트로 구현하여 탐색하도록 했다.
  • 확실히 속도와 공간 복잡도에 이점은 있다. (문제 난이도가 쉬워 구현도 쉬웠다.)
• 코드

#include <iostream>
#include <vector>

// def
#define COM_MAX_COUNT 100
#define START_COM 1
#define DEBUG_MODE 0

// method
int Infection(std::vector<int> graph[])
{
	int answer = -1;
	
	bool visited[COM_MAX_COUNT + 1] = { false, };
	std::vector<int> stack;
	stack.push_back(START_COM);

#if DEBUG_MODE
	std::vector<int> vistedHistory;
#endif

	while (!stack.empty())
	{
		int curNode = stack.back();
		stack.pop_back();

#if DEBUG_MODE
		std::cout << "curNode : " << curNode << "\n";
		vistedHistory.push_back(curNode);
#endif
		answer++;
		visited[curNode] = true;
		
		std::vector<int>::iterator iter;
		for (iter = graph[curNode].begin(); iter != graph[curNode].end(); ++iter)
		{
			// not visted node
			if (false == visited[*iter])
			{
				visited[*iter] = true;
				stack.push_back(*iter);
			}
		}
	}

	return answer;
}

int main()
{
	std::ios::sync_with_stdio(false);

	int comCnt = 0;
	int connCnt = 0;
	
	std::cin >> comCnt;	
	std::cin >> connCnt;

	std::vector<int> graphVec[COM_MAX_COUNT+1];

	for (int n = 0; n < connCnt; n++)
	{
		int a, b;
		a = b = 0;
		std::cin >> a >> b;

		// no direction
		graphVec[a].push_back(b);
		graphVec[b].push_back(a);
	}

	// calc
	int answer = Infection(graphVec);
	std::cout << answer;

	return 0;
}