[백준] 2606번: 바이러스(C++)

문제 링크

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

 

 

코드 구현

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

unordered_map<int, vector<int>> adjList;
unordered_set<int> visited;

void dfs(int node)
{
	// 방문 체크
	visited.insert(node);

	for (const int& neighbor : adjList[node])
	{
    	// 방문하지 않은 컴퓨터인 경우 dfs() 재귀 호출
		if (visited.find(neighbor) == visited.end())
		{
			dfs(neighbor);
		}
	}
}

int solution(int _computerCount, int _pairCount)
{	
	// 1번 컴퓨터부터 순회 시작
	dfs(1);

	// 1번 컴퓨터를 제외한 연결된 컴퓨터 수
	return visited.size() - 1;
}

int main()
{
	int computerCount, pairCount;
	
	cin >> computerCount >> pairCount;

	for (int i = 0; i < pairCount; i++)
	{
		int u, v;
		cin >> u >> v;
		adjList[u].push_back(v);
		adjList[v].push_back(u);
	}

	cout << solution(computerCount, pairCount);

	return 0;
}

 

 

해결 방법

재귀 함수를 이용한 DFS 알고리즘을 사용하였다. unordered_map으로 구현한 인접 리스트에 입력으로 들어오는 연결 정보를 넣어주고, 1번 컴퓨터부터 이웃 노드를 순회한다. 이 때, 시작을 1번 부터 하기 때문에 단방향 간선으로만 연결 정보를 넣을 시 {2, 3} {3, 1} 과 같이 1번 컴퓨터가 뒤에 오는 경우에는 재귀 함수가 바로 끝날 수 있으므로 양방향 간선으로 연결 정보를 넣어주고 이미 방문한 노드는 건너뛴다. 방문 체크는 unordered_set을 활용하여 중복이 안 되도록 하였다.

 

 

후기

처음에 단방향 간선으로만 넣고 결과가 잘 출력되어서 제출을 했는데 계속 오답이 떴는데 알고보니 양방향 간선으로 해주어야 한다는 것을 오랜 시간이 걸려 깨달았다.