백준 / 2606 / 바이러스 / C++ / 알고리즘 문제풀이

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

2606번: 바이러스

문제를 보고나서 드는 생각은 DFS로도 풀 수 있을것 같고, Union-Find로도 풀 수 있을 것 같다고 생각했는데

DFS로 문제를 풀어본지가 좀 오래된것 같아 DFS로 구현해서 풀어보았습니다.

 

컴퓨터간의 방향이 따로 없어서 인접리스트 형식으로 서로 연결되어 있게끔 데이터를 저장합니다.

그리고 문제가 1번 컴퓨터를 기준으로 시작하기 때문에 DFS(1)로 구현한 DFS함수를 호출합니다.

DFS에 들어오면 먼저 visited배열로 방문체크를 해서 한번 방문한 곳은 중복으로 방문하지 않도록 하고,

for문을 통해 현재 방문한 노드와 연결되어 있는 노드들을 찾아내고 그 노드가 방문한적이 없는 노드라면

답을 구하기 위한 comCnt 변수를 ++해주고 DFS(방문할노드)로 깊이우선탐색을 하게되면 답을 구할 수 있었습니다!

예제입력 같은 경우에 4,7번 노드는 1번과 연결되어 있지 않기때문에 아예 방문하지 않습니다. 

 

★잘못된 설명이 있다면 언제든지 지적해주세요 ! 또한, 질문 주시는 부분은 제가 아는선에서 상세하게 

설명드리겠습니다~!

 

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int N,M;
vector<int> comLinked[101];
bool visited[101] = { false };
static int comCnt = 0;
 
void DFS(int x)
{
    visited[x] = true;
    
    for (int i = 0; i < comLinked[x].size(); i++)
    {
        int cur = comLinked[x][i];
        if (visited[cur] == false)
        {
            comCnt++;
            DFS(cur);
        }
    }
}
 
 
 
int main()
{
    cin >> N >> M;
 
    for (int i = 1; i <= M; i++)
    {
        int a, b;
        cin >> a >> b;
        comLinked[a].push_back(b);
        comLinked[b].push_back(a);
    }
    
    DFS(1);
 
    cout << comCnt << endl;
 
}