[DFS/BFS/완전탐색] 2606번 - 바이러스

[백준] 2606번 - 바이러스

풀이 시간: 10분 이내

(풀이1) BFS 이용

이 문제는 노드 1이 포함된 그래프에서 1을 제외한 노드의 수를 구하는 문제다.

해당 문제는 입력받은 간선 정보를 통해 그래프(2차원 리스트)를 만들고 DFS/BFS로 문제를 풀 수 있다.

 

1) 문제 해결 아이디어

아래 코드는 BFS로 구현한 방법이다.

 

2) 소스코드

from collections import deque

n = int(input())  # 컴퓨터 수
m = int(input())  # 컴퓨터 간선 수
graph = [[] for _ in range(n + 1)] 
visited = [False] * (n + 1) 
res = 0  # 1이 감염시킨 컴퓨터 수

for i in range(m):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

def bfs(v):
  queue = deque()
  # 시작 노드 삽입, 방문 처리
  queue.append(v)
  visited[v] = True

  while queue:
    global res  # 전역변수 사용    
    # 노드 꺼내기
    v = queue.popleft()
    res += 1 
    # 인접노드 탐색
    for i in graph[v]:
      # 방문하지 않은 노드라면
      if not visited[i]:
        # 삽입, 방문처리
        queue.append(i)
        visited[i] = True
        
bfs(1)
print(res - 1)

 

(풀이2) DFS 이용

1) 문제 해결 아이디어

아래 코드는 DFS로 구현한 방법이다. 

이 문제는 DFS로 구현한 방법이 메모리, 시간 측면에서 모두 더 효율적이었다.

 

2) 소스코드

n = int(input())  # 컴퓨터 수
m = int(input())  # 컴퓨터 간선 수
graph = [[] for _ in range(n + 1)] 
visited = [False] * (n + 1) 
res = 0  # 1이 감염시킨 컴퓨터 수

for i in range(m):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

# DFS
def dfs(v):
  global res  # 전역변수 사용
  # 현재 노드 삽입, 방문처리
  visited[v] = True
  res += 1
  
  # 인접 노드 검사
  for i in graph[v]:
    # 방문하지 않은 노드라면
    if not visited[i]:
      dfs(i)  # 해당 노드 재귀 호출  
  
dfs(1)
print(res - 1)