문제 출처 : https://www.acmicpc.net/problem/2606
난이도 : 실버 3

---

문제 파악

그래프와 간선 정보들이 주어졌을 때, 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력해야 하는 문제이다.

풀이 사고 흐름 -> 그래프와 간선 정보? BFS?,DFS? 되시겠다.

그렇다면 BFS, DFS 중에서는?
둘다 가능하겠지만 깊이와 너비중 무엇이 더 이 문제에 적절할까?

이 질문에 대한 확신이 서지 않아 GPT에게 물어봤다.
GPT의 답으로는
결론은 둘 다 가능하고 시간차이도 아주 미세하다고 하여 두 방법 다 풀어보았다.

DFS 풀이

DFS는 “현재 노드에서 갈 수 있는 만큼 깊게” 들어가며 방문한다.

여기서는 방문할 때마다 cnt를 올리되,
1번 컴퓨터는 감염 대상에서 제외해야 하므로 cnt = -1로 시작해서
1번까지 포함해 방문한 총 방문 횟수에서 1을 빼는 효과를 만든다.

import sys
input = sys.stdin.readline

N = int(input())

E = int(input())

computers = []
for _ in range(N+1):
    computers.append([])

# print(computers) # [[], [], [], [], [], [], [], []]


for _ in range(E):
    u, v = map(int,input().split())
    computers[u].append(v)
    computers[v].append(u)

# print(computers) # [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]

visited = []
for _ in range(N+1):
    visited.append(False)
cnt = -1 # 처음 1번 컴퓨터는 감염대상에서 제외해야 하기에 -1부터 출발

def dfs(u):
    global cnt
    visited[u] = True
    cnt += 1
    for node in computers[u]:
        if visited[node] == False:
            dfs(node)

dfs(1)

print(cnt)

---

BFS 풀이

BFS는 큐를 이용해서 “현재 노드와 인접한 노드들을 순서대로” 방문한다.

BFS에서는 더 직관적으로,
“새로 감염되는 컴퓨터(=처음 방문하는 컴퓨터)”가 생길 때마다 cnt를 1씩 올린다.
이 방식이면 시작점 1번은 카운트하지 않게 자연스럽게 처리된다.

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

N = int(input())
E = int(input())

computers = []
for _ in range(N+1):
    computers.append([])

# print(computers) # [[], [], [], [], [], [], [], []]


for _ in range(E):
    u, v = map(int,input().split())
    computers[u].append(v)
    computers[v].append(u)

# print(computers) # [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]

visited = [False] * (N+1)
cnt = 0

def bfs(u):
    global cnt 
    queue = deque([u])
    visited[u] = True

    while queue:
        node = queue.popleft()

        for neighbor in computers[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                cnt += 1
                queue.append(neighbor)

bfs(1)
print(cnt)

---

위 : DFS
아래 : BFS

시간이 32ms 가 차이 나지만 표본이 커지면
인접 리스트 기준

• DFS: O(N + M)
• BFS: O(N + M)

실행시간은 구현/상수/환경에 따라 약간 차이날 수 있지만, 알고리즘 자체가 “DFS가 더 빠르다/느리다”로 결론나는 문제는 아니라고 한다.