[BaekJoon 2606][⚪3] 바이러스

❓ 문제

백준 2606 - “바이러스”

🎯 난이도

Silver ⚪3

🧠 풀이

1. 내 풀이 (DFS)

- 알고리즘

• Graph Search, DFS

- 설명

DFS 그래프 탐색을 이용한 풀이이다.

DFS는 보통 재귀 혹은 stack을 사용하는 방식이 있는데, 이번 풀이는 재귀를 사용하는 방식이다. 방문 노드를 체크해가며, 새로운 노드를 방문할 때마다 카운트를 늘려가는 방식으로 원하는 결과값을 도출했다.

컴퓨터의 수가 N <= 100라서 재귀 방식으로도 스택 오버플로우에서 안전하다는 것을 알고 채택한 방식이지만, 보통 더 안전하게 하기 위해서는 stack을 사용하거나 BFS 방식을 사용하는 것이 좋다.

각 노드를 한 번씩 방문하므로, 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>


using namespace std;

int DFS(const vector<vector<int>>& vecNetwork, vector<bool>& vecVisit, int iNode);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iCom{}, iPair{};
    cin >> iCom >> iPair;

    vector<vector<int>> vecNetwork(iCom + 1);
    vector<bool> vecVisit(iCom + 1);
    while(iPair--)
    {
        int iNode1{}, iNode2{};
        cin >> iNode1 >> iNode2;

        vecNetwork[iNode1].push_back(iNode2);
        vecNetwork[iNode2].push_back(iNode1);
    }

    cout << DFS(vecNetwork, vecVisit, 1) - 1;

    return 0;
}

int DFS(const vector<vector<int>>& vecNetwork, vector<bool>& vecVisit, int iNode)
{
    int iCnt{ 1 };
    vecVisit[iNode] = true;

    for(int iNext : vecNetwork[iNode])
    {
        if(!vecVisit[iNext])
        {
            iCnt += DFS(vecNetwork, vecVisit, iNext);
        }
    }

    return iCnt;
}

---

2. 추가 풀이 (BFS)

- 알고리즘

• Graph Search, BFS

- 설명

BFS 그래프 탐색을 이용한 풀이이다.

BFS는 보통 'queue' 컨테이너를 사용하며, 'FIFO'의 특성을 이용하고 로직은 기본적으로 'DFS'와 동일하다.

기본적으로 재귀의 DFS 방식보다는 구현 방식이 좀 더 복잡하고, queue라는 컨테이너를 추가적으로 사용해야 하는 점이 있지만, 스택 오버플로우에서 안전하고 최단 거리를 보장하는 장점이 있다.

위와 같이 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>

#include <queue>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iCom{}, iPair{};
    cin >> iCom >> iPair;

    vector<vector<int>> vecNetwork(iCom + 1);
    vector<bool> vecVisit(iCom + 1);
    while(iPair--)
    {
        int iNode1{}, iNode2{};
        cin >> iNode1 >> iNode2;

        vecNetwork[iNode1].push_back(iNode2);
        vecNetwork[iNode2].push_back(iNode1);
    }

    int iCnt{};
    queue<int> qBFS{};

    qBFS.push(1);
    vecVisit[1] = true;

    while(!qBFS.empty())
    {
        int iFront = qBFS.front();
        qBFS.pop();

        for(int iNext : vecNetwork[iFront])
        {
            if(!vecVisit[iNext])
            {
                vecVisit[iNext] = true;
                qBFS.push(iNext);

                ++iCnt;
            }
        }
    }

    cout << iCnt;

    return 0;
}

---

💭 후기

최단 거리 문제도 아니고, 단순 노드 카운팅에 범위도 좁아서 스택 오버플로우에서 안전한 문제라, 재귀의 DFS 방식을 사용해 풀었다. 문제가 좀만 더 복잡해지거나 조건이 까다로워지면 이렇게 쉬운 방식으로는 풀리지 않으므로, 어떤 방식을 채택할지는 잘 생각해보도록 하자.

🔗 참고자료

• DFS, BFS