백준 2606: 바이러스 Python (DFS, BFS)

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

2606번: 바이러스

 

이번 문제는 bfs나 dfs 두 가지 모두 사용 가능하다.

 

먼저, dfs로 푼 코드이다.

여기서 조심할 것은 1번 컴퓨터가 바이러스를 옮긴 컴퓨터의 수를 구하는 것이기 때문에, 바이러스에 걸린 컴퓨터 수를 구할 때 1번 컴퓨터는 제외해야 한다.

import sys
input = sys.stdin.readline


def dfs(v):
    global cnt
    visited[v] = 1
    for w in range(1, N+1):
        if adj[v][w] and not visited[w]:
            cnt += 1
            dfs(w)


N = int(input())    # N: 컴퓨터의 수
M = int(input())    # M: 직접 연결돼 있는 컴퓨터 쌍의 수
adj = [[0] * (N+1) for _ in range(N+1)]     # 인접행렬
visited = [0] * (N+1)   # 바이러스 감염여부 체크
cnt = 0
for _ in range(M):
    a, b = map(int, input().split())
    adj[a][b] = adj[b][a] = 1   # 방향성 없음

dfs(1)  # 1번 컴퓨터부터 시작
print(cnt)

 

 

두 번째, bfs로 푼 코드

import sys
input = sys.stdin.readline


def bfs(v):
    global cnt
    q = [v]
    visited[v] = 1

    while q:
        v = q.pop(0)
        cnt += 1
        for w in range(1, N+1):
            if adj[v][w] and not visited[w]:
                visited[w] = 1
                q.append(w)


N = int(input())    # N: 컴퓨터의 수
M = int(input())    # M: 직접 연결돼 있는 컴퓨터 쌍의 수
adj = [[0] * (N+1) for _ in range(N+1)]     # 인접행렬
visited = [0] * (N+1)   # 바이러스 감염여부 체크
cnt = 0
for _ in range(M):
    a, b = map(int, input().split())
    adj[a][b] = adj[b][a] = 1   # 방향성 없음

bfs(1)
print(cnt-1)

 

결론

dfs, bfs를 연습해보기에 좋은 문제이다.

bfs가 dfs보다 훨씬 처리 속도가 빠를 것이라고 예상했는데, 이 문제에서는 입력 값이 크지 않아서 그런지 오히려 bfs 처리속도가 더 느렸다.