[백준(python)] 2606 바이러스

📌 난이도, 유형

난이도 : 실버3
유형 : DFS, BFS
시간제한 : 1초
메모리제한 : 128MB

---

📌 문제설명

---

📌 입출력 예

---

📄 코드

BFS(Breadth-First Search) 풀이

from collections import deque

def bfs():
    global result
    while q:
        cur = q.popleft()
        for i in range(N + 1):
            if not visited[i] and graph[cur][i]:
                result = result + 1
                visited[i] = True
                q.append(i)
# 컴퓨터의 수
N = int(input())
# 간선의 수
M = int(input())

graph = [[False] * (N + 1) for _ in range(N + 1)]
visited = [False] * (N + 1)

for _ in range(M):
    a,b = map(int, input().split())
    graph[a][b] = True
    graph[b][a] = True

result = 0
q = deque([1])
visited[1] = True
bfs()
print(result)

DFS(Depth-First Search) 풀이

def dfs(idx):
    global result
    visited[idx] = True
    print(idx, end=' ')
    for i in range(N + 1):
        if not visited[i] and graph[idx][i]:
            result = result + 1
            dfs(i)            

# 컴퓨터의 수
N = int(input())
# 간선의 수
M = int(input())

graph = [[False] * (N + 1) for _ in range(N + 1)]
visited = [False] * (N + 1)

for _ in range(M):
    a,b = map(int, input().split())
    graph[a][b] = True
    graph[b][a] = True

result = 0
dfs(1)
print(result)

---

📝 해설

시작노드는 1이라고 문제에 주어졌다.

어차피 간선(edge)으로 연결이 안된 정점(vertex)은 영향을 주지 않기 때문에 일반적인 DFS, BFS 문제로 풀면 된다.

결과값 같은 경우에는 1은 포함이 되면 안 되기 때문에 조건문 안에 넣어주었다.

DFS가 BFS보다 조금 더 빠름