2606 : 바이러스 (C++)

2606번: 바이러스

---

먼저 DFS로 푼 방식이며

 

인접리스트를 활용하였다.

 

1번 컴퓨터를 통해 감염되는 컴퓨터의 수를 출력하므로

 

마지막에 센 숫자에서 1을 빼준다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int cnt = 0;

void dfs(int start, vector<int> graph[], bool check[]) {
    check[start] = true;
    cnt++;
    for(int i = 0; i < graph[start].size(); i++) {
        int next = graph[start][i];
        if(check[next] == false) {
            dfs(next, graph, check);
        }
    }
}

int main() {
    int N, M;
    int start = 1;

    cin >> N >> M;

    vector<int> graph[N + 1];
    bool check[N + 1];
    fill(check, check+N+1, false);

    for(int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    for(int i = 1; i <= N; i++) {
        sort(graph[i].begin(), graph[i].end());
    }

    dfs(start, graph, check);

    printf("%d\n", cnt - 1);
}

 

다음 밑의 방식은 인접리스트를 활용한 BFS로 푼 방식이다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

int cnt = 0;

void bfs(int start, vector<int> graph[], bool check[]) {
    queue<int> q;
    q.push(start);
    check[start] = true;

    while(!q.empty()) {
        int tmp = q.front();
        q.pop();
        cnt++;
        for(int i = 0; i < graph[tmp].size(); i++) {
            if(check[graph[tmp][i]] == false) {
                q.push(graph[tmp][i]);
                check[graph[tmp][i]] = true;
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> graph[n + 1];
    bool check[n + 1];
    fill(check, check+n+1, false);

    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    for(int i = 1; i <= n; i++) {
        sort(graph[i].begin(), graph[i].end());
    }

    bfs(1, graph, check);
    printf("%d", cnt-1);
}

 

다음은 인접행렬과 DFS로 푼 방식.

#include<iostream>
#define MAX_VALUE 101

using namespace std;

int N, M;
int mat[MAX_VALUE][MAX_VALUE];
int visit[MAX_VALUE];
int cnt = 0;

void dfs(int start) {
    visit[start] = 1;
    cnt++;

    for(int i = 1; i <= N; i++) {
        if(visit[i] == 0 && mat[start][i] == 1) {
            dfs(i);
        }
    }
}

int main() {
    cin >> N >> M;

    for(int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        mat[u][v] = mat[v][u] = 1;
    }

    dfs(1);
    cout << cnt - 1;

    return 0;
}

 

마지막으로 인접행렬과 BFS로 푼 방식

#include<iostream>
#include<queue>
#define MAX_VALUE 101

using namespace std;

int N, M;
int mat[MAX_VALUE][MAX_VALUE];
int visit[MAX_VALUE];
int cnt = 0;

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visit[start] = 1;

    while(!q.empty()) {
        start = q.front();
        cnt++;
        q.pop();
        for(int i = 1; i <= N; i++) {
            if(visit[i] == 0 && mat[start][i] == 1) {
                q.push(i);
                visit[i] = 1;
            }
        }
    }
}

int main() {
    cin >> N >> M;

    for(int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        mat[u][v] = mat[v][u] = 1;
    }

    bfs(1);
    cout << cnt - 1;

    return 0;
}