백준 2606 바이러스 C++

- 문제

문제 보러가기

DFS 자료구조 정리
DFS를 정리하며 간단한 그래프 이론 문제를 하나 풀어보았다.

- 문제 풀이

• DFS(Depth First Search)는 재귀함수를 통해 구현 하였다.
• 자료구조는 입력받는 노드의 수가 100개로 정해져있으므로 이중배열의 크기를 각각 101로 하드코딩해주었다.

- 코드

#include <iostream>
using namespace std;

bool computer[101][101] = {0, };
bool visited[101] = {0, };
int nodeNum, rowNum;
int result = 0;

void dfs(int start){
    result++;
    visited[start] = 1;
    for(int i = 1; i <= nodeNum; i++){
        if(computer[start][i] && !visited[i])
            dfs(i);
    }
}

int main()
{
    cin >> nodeNum >> rowNum;
    int start, end;
    for(int i = 0; i < rowNum; i++){
        cin >> start >> end;
        computer[start][end] = 1;
        computer[end][start] = 1;
    }

    dfs(1);

    cout << result - 1;
    return 0;
}