백준 2606번 : 바이러스

# 문제 : https://www.acmicpc.net/problem/2606

from collections import deque
# 백준 2606번 : 바이러스
n = int(input())
m = int(input())

#adjacent 배열로 구현
# computers=[[0]*(n+1) for _ in range(n+1)]
# for _ in range(m):
#   a,b = map(int, input().split())  # input한 값들을 int 함수로 바꿔주는 map 함수로 구현
#   computers[a][b] = 1
#   computers[b][a] = 1
# 풀이 : https://velog.io/@wjdtmdgml/%EB%B0%B1%EC%A4%80%EB%B0%94%EC%9D%B4%EB%9F%AC%EC%8A%A42606%EB%B2%88Python%ED%8C%8C%EC%9D%B4%EC%8D%ACBFS

#adjacent 리스트로 구현
computers = [[] for _ in range(n+1)]  # [[]*(n+1)]이랑 다름!
visited = [0]*(n+1)

for _ in range(m):
  a,b = map(int,input().split())
  computers[a].append(b)
  computers[b].append(a)
  
  # 풀이 : https://hei-jayden.tistory.com/103


# BFS로 구현 (방문처리 배열, deque)
def BFS(computers, start):
  queue = deque()
  queue.append(start)
  count = 0
  
  while queue:
    now = queue.popleft()
    visited[now] = 1
    
    for i in computers[now]:
      if visited[i] == 0:
        visited[i] = 1
        queue.append(i)
        count += 1
  print(count)

BFS(computers,1)

 

코딩 테스트를 준비하고자  가장 비중이 많다고 하는 BFS와 DFS를 공략해보려고 하였다.

하지만 프로그래머스의 레벨2 문제에 벽을 느끼고 만 나머지 기초문제 부터 차근차근 풀기로 결정했다;;

사실 BFS의 개념은 알고 있었으나 이를 어떠한 경우에 사용해야 하며, 이것을 구현하는 원리도 알지 못했다.

이번 문제를 풀면서(사실상 푼건 아니고 해설을 보고 공부함) BFS에 필요한 것들이 무엇인지 알 수 있었다.

 

BFS를 구현하기 위해 필요한 것

• 방문처리를 할 visited 리스트
• 노드의 값을 저장할 행렬 혹은 리스트

이때 노드를 저장하는 방법으로는 행렬과 리스트가 있으나 둘 다 장단점이 있다.

출처 : https://ghkvud2.tistory.com/4?category=826403 

BFS와 DFS의 기초 개념 -2

이 분의 글에 특징들이 알기 쉽게 정리되어 있다. (필자도 덕분에 이해하는데 도움이 되었던 자료이다)

또한 코드에서 알 수 있듯이 visited나 computers(노드의 값을 저장하는 리스트)의 크기가 n+1인 이유는

해당 노드의 번호를 인덱스 값과 일치시키기 위해서이다.

인덱스는 0부터 시작하므로 노드의 번호와 일치하지 않기 때문에 n+1을 통해 값을 일치시키면 코드 작성에 더 편하다.

 

이차원 배열 생성할 때

• computers = [[] for _ in range(n+1)]   (O)
• computers = [[] * (n+1)]  (X : IndexError 발생, 결과 값 = [ [ ] ])