[백준/BOJ] 백준 코딩 알고리즘 2606번 바이러스 Python 그래프와 순회

 

 

 

본 문제는 1번 컴퓨터에서 시작했을 때 연결로 인해 감염이 발생하는 컴퓨터의 수를 구하는 문제이다
감염 == 방문 개념으로 생각하면 기본적인 DFS, BFS 문제로 접근하여 풀 수 있다

그에 따라 각 풀이는 아래와 같다

 

BFS를 이용하는 경우

while queue:
  front = queue.popleft() # queue의 가장 앞 원소 front 가져오기
  connect_list = [i for i in coms[front]] # front와 연결된 컴퓨터 목록 가져오기

  for c in connect_list: # 연결된 컴퓨터 목록에 대해서 방문한 적이 없다면 전파
    if not visited[c]:
      visited[c] = True
      queue.append(c)

 

• BFS를 이용하는 경우
• queue의 front에서 빼와 방문하고자 하는 노드를 정한다 (dequeue)
• 방문하는 노드를 visited 배열에 True값을 넣어 방문처리를 한다
• 방문하는 노드와 연결된 노드들을 queue에 넣는다 (enqueue)
• queue가 빌 때 까지 이 과정을 반복한다

 

DFS를 이용하는 경우

def dfs(k):
  visited[k] = True
  for c in coms[k]:
    if not visited[c]:
      dfs(c)
      
dfs(1)

 

• DFS를 이용하는 경우
• 별도의 stack 자료구조를 사용하지는 않는다 -> 함수 호출 및 반환 구조 자체가 stack이기 때문
• 방문하는 노드를 visited 배열 값을 True로 함으로써 방문 처리를 한다
• 해당 방문 노드와 연결된 노드들을 for문으로 탐색한다 -> 방문하지 않았을 시 재귀 호출로 넘긴다
• 만약 더이상 방문할 수 없는 노드까지 방문한다면, 다시 stack 구조에 따라 재귀적으로 돌아간다

 

참고

노드들이 연결된 '그래프'를 저장 및 표현하는 방식에는 크게 2가지가 있다
인접 리스트 방식와 인접 행렬 방식이 있다

인접 행렬
노드와 노드 간의 연결 여부를 저장하는데 용이
엣지의 개수와 상관 없이 O(V^2) 의 공간복잡도를 차지
Dense한 그래프를 표현하기에 적합
그래프에 노드가 자주 추가/삭제되지 않는 경우에 적합

인접 리스트
노드와 노드 간의 방향 여부까지 고려할 수 있도록 각 노드에서 연결된 노드를 저장한다
공간복잡도 O(V+E)
Sparse한 그래프를 표현하기에 적합
그래프에 노드가 자주 추가/삭제되는 경우에 적합

 

---

 

전체 코드

import sys
from collections import defaultdict, deque

def input():
  return sys.stdin.readline().rstrip()

N = int(input())
visited = [False] * (N + 1) # 방문(감염) 정보를 저장

coms = defaultdict(list) # 연결 정보를 저장
for _ in range(int(input())):
  A, B = map(int, input().split())
  coms[A].append(B)
  coms[B].append(A)

queue = deque([1]) # 시작 
visited[1] = True

### BFS를 이용하는 경우
while queue:
  front = queue.popleft() # queue의 가장 앞 원소 front 가져오기
  connect_list = [i for i in coms[front]] # front와 연결된 컴퓨터 목록 가져오기

  for c in connect_list: # 연결된 컴퓨터 목록에 대해서 방문한 적이 없다면 전파
    if not visited[c]:
      visited[c] = True
      queue.append(c)

### DFS를 이용하는 경우
# def dfs(k):
#   visited[k] = True
#   for c in coms[k]:
#     if not visited[c]:
#       dfs(c)

# dfs(1)

# 결과 출력
print(sum(visited) - 1) # 1을 제외한 감염된 컴퓨터의 수