https://www.acmicpc.net/problem/2606

🥚문제

---

🥚입력/출력

---

🍳코드 (BFS 버전)

# 바이러스
n = int(input()) # 컴퓨터의 수
graph = [[0]*(n+1) for i in range(n+1)]
for i in range(int(input())):
    a, b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1
visited = [False]*(n+1)

# 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수
def bfs():
    count = 0 # 컴퓨터의 수
    queue = [1] # 1번 컴퓨터 큐 삽입
    visited[1] = True # 방문 표시
    while queue:
        v = queue.pop(0) # 큐 팝
        for i in range(n+1):
            if graph[v][i] == 1 and not visited[i]:
                queue.append(i) # 큐 삽입
                visited[i] = True # 방문 표시
                count += 1 # 증가
    return count

print(bfs())

---

🍳코드 (DFS 버전)

# 바이러스
n = int(input()) # 컴퓨터의 수
graph = [[0]*(n+1) for i in range(n+1)]
for i in range(int(input())):
    a, b = map(int, input().split())
    graph[a][b] = graph[b][a] = 1
visited = [False]*(n+1)

def dfs(v):
    stack = []
    stack.append(v) # 스택에 v 삽입
    visited[v] = True # 방문 표시
    while stack:
        V = stack.pop()
        #print(V, end=' ')
        # 인접 노드들 삽입
        for i in range(n+1):
            if graph[V][i] == 1 and not visited[i]:
                dfs(i)

dfs(1) # 1번 컴퓨터부터 시작
print(visited.count(True) - 1) # 1번 컴퓨터는 빼준다

---

🧂아이디어

• ❗ bfs, dfs를 각각 언제 사용할 것인가? ❗