[BaekJoon] 2606번 - 바이러스 [Java][C++]

문제 링크

---

1. 문제 풀이

바이러스를 노드, 연결 정보를 간선으로 간주한 그래프에서 1번 노드와 직간접적으로 연결된 다른 노드의 수를 구하는 문제로 생각할 수 있다. BFS 또는 DFS를 활용해서 방문한 노드의 수를 카운팅해주면 해결할 수 있다. 노드의 수가 크지 않아서 인접 행렬을 활용해서 구현했다.

---

2. 코드

1. BFS [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        boolean[][] adj = new boolean[1 + N][1 + N];

        int M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            adj[x][y] = adj[y][x] = true;
        }

        int result = bfs(N, adj);
        System.out.println(result);
    }

    static int bfs(int N, boolean[][] adj) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(1);

        boolean[] visited = new boolean[1 + N];
        visited[1] = true;

        int cnt = 0;

        while (!q.isEmpty()) {
            int node = q.poll();

            for (int next = 1; next <= N; next++) {
                if (adj[node][next] && !visited[next]) {
                    q.offer(next);
                    visited[next] = true;
                    cnt++;
                }
            }
        }

        return cnt;
    }
}

2. DFS [Java]

import java.io.*;
import java.util.*;

public class Main {

    static int N;
    static boolean[][] adj;
    static boolean[] visited;
    static int cnt = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        adj = new boolean[1 + N][1 + N];

        int M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            adj[x][y] = adj[y][x] = true;
        }

        visited = new boolean[1 + N];
        dfs(1);

        System.out.println(cnt - 1);
    }

    static void dfs(int node) {
        visited[node] = true;
        cnt++;

        for (int next = 1; next <= N; next++) {
            if (adj[node][next] && !visited[next]) {
                dfs(next);
            }
        }
    }
}

3. BFS [C++]

#include <bits/stdc++.h>
using namespace std;

bool adj[1 + 100][1 + 100];
bool visited[1 + 100];

int bfs(int n) {
    queue<int> q;
    q.push(1);

    visited[1] = true;

    int cnt = 0;

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        for (int next = 1; next <= n; next++) {
            if (adj[node][next] && !visited[next]) {
                q.push(next);
                visited[next] = true;
                cnt++;
            }
        }
    }

    return cnt;
}

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

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        adj[x][y] = adj[y][x] = true;
    }

    int cnt = bfs(n);
    cout << cnt << '\n';
}

4. DFS [C++]

#include <bits/stdc++.h>
using namespace std;

int n;
bool adj[1 + 100][1 + 100];
bool visited[1 + 100];
int cnt = 0;

void dfs(int node) {
    visited[node] = true;
    cnt++;

    for (int next = 1; next <= n; next++) {
        if (adj[node][next] && !visited[next]) {
            dfs(next);
        }
    }
}

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

    int m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        adj[x][y] = adj[y][x] = true;
    }

    dfs(1);
    cout << cnt - 1 << '\n';
}

---