[백준 2606번] 바이러스 (BFS, C++/Python)

1에서 시작해서 방문할 수 있는 모든 노드를 찾는 문제.

C++ 풀이

#include <bits/stdc++.h>

using namespace std;
vector<int> v[101];
bool visited[101];
queue<int> q;
int cnt = 0;
void bfs()
{
    visited[1] =true;
    q.push(1);
    
    while(!q.empty())
    {
        int a = q.front();
        q.pop();
        for(int i =0;  i<v[a].size(); i++)
        {
            if(visited[v[a][i]]== false)
            {
                cnt++;
                visited[v[a][i]] = true;
                q.push(v[a][i]);
            }
        }
    }
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    ifstream in("input.txt");
    int N,M;
    in >> N >> M ;
    for(int i = 0 ; i < M; i++)
    {
        int a, b;
        in >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    bfs();

    cout << cnt;
}

Python 풀이

import sys
from collections import deque
input = sys.stdin.readline

N = int(input().strip())
M = int(input().strip())

data = [[] for _ in range(N+1)]
visited = [False] * (N+1)
dq = deque()
for _ in range(M):
    node1, node2 = map(int,input().split())
    data[node1].append(node2)
    data[node2].append(node1)

def bfs(data,visited):
    dq.append(1)
    visited[1] = True
    cnt =0
    while dq:
        node=dq.popleft()
        for i in range(len(data[node])):
            if visited[data[node][i]] == False:
                visited[data[node][i]] = True
                cnt+=1
                dq.append(data[node][i])
    return cnt
print(bfs(data,visited))