[코딩테스트 연습(Python)] 백준 2606번_바이러스(DFS/BFS)

1. DFS를 활용한 풀이

import sys

input = sys.stdin.readline

n = int(input())
k = int(input())

graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
cnt = 0

# 각 노드들 마다 연결된 값 append
# graph 완성
for i in range(k):
    a, b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

# dfs구현
def dfs(virus):
    # def 안에서 cnt를 사용하기 위해 global 적용
    global cnt
    # 방문한 노드를 True로 변경
    visited[virus] = True
    
    # [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]
    for i in graph[virus]:
        if not visited[i]:
            cnt += 1
            dfs(i)

dfs(1)
print(cnt)

 

2. BFS를 활용한 풀이

import sys
# bfs알고리즘에선 queue 자료구조 사용
from collections import deque

n = int(input())
k = int(input())

graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
cnt = 0

for i in range(k):
    a,b = map(int,sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

# bfs알고리즘
def bfs(virus):
    global cnt
    queue = deque()
    queue.append(virus)
    
    while queue:
        x = queue.popleft()
        visited[x] = True
        
        # [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]
        for i in graph[x]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)
                cnt += 1
    return cnt

print(bfs(1))

 

3.풀이

두 풀이 방식 모두 graph 변수를 생성해 주어진 모든 노드들을 담는 것은 같다.

[[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]

 

DFS방식의 경우 재귀함수를 활용해 순서대로 모든 노드를 방문한다.

예를 들어 1부터 시작할 경우 1에 연결된 모든 노드 2-> 3, 5  -> 5 (3은 이미 방문) -> 6(1,2는 이미 방문)

이런식으로 첫번째로 마주한 노드를 모두 먼저 방문한 후 다음 순서인 5를 방문한다. 하지만 이미 깊이 우선 탐색에 의해 2를 방문하면서 연결된 2와 연결된 5를 방문했기 때문에 반복문은 종료되고 cnt를 반환하게 된다.

 

 

BFS 방식의 경우 deque를 사용하여 너비 우선 탐색을 한다.

예를 들어 DFS의 경우 1과 연결된 노드 2에서 한번 더 들어가 2와 연결된 3, 5 그리고 3과 연결된 5, 5와 연결된 6 이런식으로 i번째 노드마다 최대 깊이로 모두 탐색해버리고 다음 i로 넘어간다면

 

1. BFS의 경우 1과 연결된 2,5를 먼저 방문 -> 방문한 1을 queue에서 제외, 2,5를 queue에 넣음

2. 2와 연결된 3,5(1은 이미 방문)를 방문하고 5와 연결된 6을 queue에 넣음, 3,5를 queue에서 제외 (3과 연결된 2와 5와 연결된 1,2는 이미 방문했기 때문에 queue에 넣지 않음)

3. 반복문 종료 (두 번째로 queue에 넣은 2,5중 5는 노드 2를 DFS방식으로 방문하며 이미 queue에서 빠졌기 때문에 방문할 필요 없음)

 

이런식으로 진행된다.