[백준1926&파이썬] BFS를 활용하여, 연결된 노드의 너비를 세는 방법

# 문제

백준 1926번 그림, 파이썬 

1926번: 그림

# 코드

import sys
from collections import deque

n,m = map(int,sys.stdin.readline().split()) # n 세로크기 , m 가로크기

board = list()
visit = [[ False for j in range(m) ] for i in range(n)]
for i in range(n) :
  row = list(map(int,sys.stdin.readline().split()))
  board.append(row)

dirs = [
  (-1,0),(0,1),(1,0),(0,-1)
  ]

max_size = 0
cnt = 0

for row in range(len(visit)) :
  for col in range(len(visit[row])) :
    if visit[row][col] == False and board[row][col] == 1:
      dq = deque()
      start = (row,col)
      local_size = 1
      visit[row][col] = True
      dq.append(start)
      cnt +=1

      while len(dq) != 0 :
        cur = dq.popleft()
        for dir in dirs :
          next = (cur[0]+dir[0], cur[1]+dir[1])
          if 0 <= next[0] < n and 0 <= next[1] < m:
            if visit[next[0]][next[1]] == False and board[next[0]][next[1]] == 1:
              dq.append(next)
              local_size +=1
              visit[next[0]][next[1]] = True
      max_size = max(max_size,local_size)

# print(board)
# print(visit)

# print("cnt : ", cnt)
# print("size : ", max_size)

print(cnt)
print(max_size)

 

# 풀이

## queue보다는 deque를 사용하자

• 예전에 공부했던거와 같이 queue는 느리다. 그렇기 때문에 deque를 사용해야한다는 것을 잊지 말자

 

## 각 단계별로 deque를 만들어 사용하자

• 전역에서 deque를 사용하는 것이 아닌, for문으로 첫 방문 대상을 탐색하고, 첫 방문이 결정되면 해당 Loop안에서 deque를 구성하고 bfs탐색을 하도록 하자.
• 최소한 이번 문제를 해결함에 있어서, 복잡한 생각을 하지 않을 수 있었다. 
• 이렇게 구성함으로써 문제 내에서 찾아야 했던 그림의 개수를 Loop 진입점을 count하는 것으로 쉽게 해결 할 수 있었다.

 

## 연결 노드의 집단의 개수는 deque에 들어가는 것으로 count 한다.

• 이전 단계를 기억하게 하는 프로시져 풀이방법에 얽매이다 보니까 자꾸 산으로 갈뻔했다. 
• 프로시져 방법은 몇단계내(최단 단계)를 활용할때는 좋은 접근이지만, 집단의 총 갯수를 세어야 할때는 적절한 방법이 아니다. 그냥 방문표시할때 하나씩 count해주자.

 

# 결론

BFS를 활용해서 그래프상의 집단의 크기를 구할 수 있고, 집단들의 개수를 셀 수 있다.