[Baekjoon] 2606번: 바이러스

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

---

 

문제 해결 과정

착안

문제를 보자마자 그래프 자료구조를 이용해 시작 정점으로부터 연결되어 있는 모든 정점을 순회하는 알고리즘인 깊이 우선 탐색 알고리즘(depth-first search, DFS), 또는 너비 우선 탐색 알고리즘(breadth-first search, BFS)을 이용해야할 것으로 판단되었다. 마침 지난 포스트에서 깊이 우선 탐색 알고리즘을 구현했었던 것을 활용(...)하여, 해당 코드를 일부 수정하여 문제를 해결할 수 있었다(변명을 하자면, 어차피 깊이 우선 탐색 알고리즘과 너비 우선 탐색 알고리즘의 시간 복잡도는 같은데, 너비 우선 탐색을 구현할 때에는 큐(queue) 자료 구조를 추가적으로 활용해야 구현하기 용이해서 그냥 기존에 구현해놓은 코드를 응용하였다...).

 

이번 문제에서는 탐색이 되는 순서는 고려하지 않고, 시작 정점으로부터 해당 정점까지 접근이 되는가의 여부만 중요하기 때문에 해당 멤버를 수정하였다. 한편, 시작 정점으로부터 깊이 우선 탐색을 수행하고 난 뒤 시작 정점을 제외하고 그래프 내의 정점 중에서 방문이 된 정점의 수를 구하는 메서드(Graph::Affected())를 추가하였다(문제에서 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 수를 출력하라고 했으므로 시작 정점은 제외).

 

구현

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <vector>

using namespace std;

struct Graph
{
	struct Vertex
	{
		vector<int> NextIndex;
		bool Visited = false;
	};

	Graph(int N)
	{
		V = vector<Vertex>(N);
	}

	void AddEdge(int From, int Dest)
	{
		V[From - 1].NextIndex.push_back(Dest);
	}

	void DFS(int index)
	{
		Vertex& currV = V[index - 1];
		currV.Visited = true;
		for (int index : currV.NextIndex)
		{
			if (!V[index - 1].Visited)
				DFS(index);
		}
	}

	int Affected()
	{
		int Count = 0;
		for (Vertex v : V)
			if (v.Visited)
				Count++;

		return Count;
	}

	vector<Vertex> V;
};


int main()
{
	int N, M;
	scanf("%d %d", &N, &M);

	Graph graph = Graph(N);

	int from, dest;
	while (M--)
	{
		scanf("%d %d", &from, &dest);
		graph.AddEdge(from, dest);
		graph.AddEdge(dest, from);
	}

	graph.DFS(1);
	printf("%d\n", graph.Affected() - 1);

	return 0;
}

 

실행 결과

* 코드를 제출한 시점과 글 작성 시점이 달라, 주석 추가 등의 이유로 실행 결과의 코드 길이는 상이할 수 있음.

 

---

 

자료 구조가 모든 알고리즘 공부의 기반이 되는 기초 지식이기는 하지만, 이 문제가 고작 정보 올림피아드 초등부 지역 본선 문제라니 우리나라 초등학생들은 정말 똑똑하고 대단한 것 같다. 우리나라 IT 분야의 앞날은 어쩌면 우리가 생각하는 것보다 훨씬 밝지 않을까 하는 생각을 해본다.