[python] 백준 2606번 : 바이러스 (DFS, BFS)

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

2606번: 바이러스

 

그래프 탐색 문제이다. 1번 컴퓨터를 통해 웜 바이러스에 걸릴 컴퓨터의 개수를 구하라고 문제에서 제시해 주었다. 즉, 1번 노드와 연결된 노드의 개수를 구하면 된다. 따라서 DFS로도 BFS로도 구현할 수 있는 문제이다. 

 

* 문제에서 연결된 컴퓨터의 정보를 제시할 때 언제가 1번부터 등장한다는 언급이 없다. 따라서

6
5
6 5
5 4
4 3
3 2
2 1

다음과 같은 input 값이 주어진 경우에는 1번 노드와 연결된 2번 노드가 graph[1]에 저장되지 않는다.

이 문제에서의 그래프는 무방향 그래프이다. 따라서 a와 b가 연결되었다는 정보를 저장한다면 반드시 graph[a]와 graph[b]에 동시에 연결 정보를 저장해야 한다.  

 

[DFS 재귀적 구현] (전역변수 count 사용)

# 컴퓨터의 수
v = int(input())
# 네트워크 쌍 개수
e = int(input())
graph = [[] for _ in range(v+1)]
for _ in range(e):
    a, b = map(int, input().split())
    # 연결된 컴퓨터의 정보가 언제가 1부터 등장한다는 보장 x
    graph[a].append(b)
    graph[b].append(a)

# 재귀적 구현
def dfs(x):
    global count
    visited[x] = True
    count += 1
    for node in graph[x]:
        if visited[node]:
            continue
        dfs(node)

count = 0
visited = [False for _ in range(v+1)]
dfs(1)
print(count-1)

 

[DFS 재귀적 구현] (지역변수 count 사용)

# 컴퓨터의 수
v = int(input())
# 네트워크 쌍 개수
e = int(input())
graph = [[] for _ in range(v+1)]
for _ in range(e):
    a, b = map(int, input().split())
    # 연결된 컴퓨터의 정보가 언제가 1부터 등장한다는 보장 x
    graph[a].append(b)
    graph[b].append(a)


# 재귀적 구현
def dfs(x, count):
    visited[x] = True
    for node in graph[x]:
        if not visited[node]:
            count = dfs(node, count+1)
    return count

visited = [False for _ in range(v+1)]
print(dfs(1, 0))

 

[DFS 스택 구현] 

stack 사용시 while 문 돌리기 전에 시작 노드 방문 처리 중요

# 컴퓨터의 수
v = int(input())
# 네트워크 쌍 개수
e = int(input())
graph = [[] for _ in range(v+1)]
for _ in range(e):
    a, b = map(int, input().split())
    # 연결된 컴퓨터의 정보가 언제가 1부터 등장한다는 보장 x
    graph[a].append(b)
    graph[b].append(a)


# 스택 구현
def dfs(x):
    stack = [x]
    visited[x] = True
    count = 0
    while stack:
        node = stack.pop()
        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                stack.append(next_node)
                count += 1
    return count

visited = [False for _ in range(v+1)]
print(dfs(1))

 

[BFS 큐 구현]

queue 사용시 while 문 돌리기 전에 시작 노드의 방문 처리 중요

from collections import deque

# 컴퓨터의 수
v = int(input())
# 네트워크 쌍 개수
e = int(input())
graph = [[] for _ in range(v+1)]
for _ in range(e):
    a, b = map(int, input().split())
    # 연결된 컴퓨터의 정보가 언제가 1부터 등장한다는 보장 x
    graph[a].append(b)
    graph[b].append(a)


# 큐 구현
def bfs(x):
    deq = deque([x])
    count = 0
    visited[x] = True
    while deq:
        node = deq.popleft()
        for next_node in graph[node]:
            if not visited[next_node]:
                visited[next_node] = True
                deq.append(next_node)
                count += 1

    return count

visited = [False for _ in range(v+1)]
print(bfs(1))