[ BOJ / 파이썬 ] 2667 단지 번호 붙이기

 

- 30분 소요

- 와 .. ㅠㅜ 실수해서 10분을 날려먹었다.. bfs처음 시작하면서 q에 첫 원소 넣을 때 해당 원소를 방문처리하는 걸 놓쳤다.

- 덕분에 이중 방문해서 예상 값보다 1씩 더 나오는 에러 잡느라 시간 걸렸다.

- 문제 자체는 단순한 bfs적용, 2583 영역 구하기랑 같은 맥락의 문제였다.

-  python list unpaking operator쓰는 법 까먹어서 검색해서 찾아옴..

 

import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
board = [list(map(int, list(input().strip()))) for _ in range(n)]
visited = [[False]*n for _ in range(n)]
q = deque([])
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
count = 0
homes_by_town = []

def bfs():
  home = 1
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 1 and not visited[nx][ny]:
        visited[nx][ny] = True
        q.append((nx, ny))
        home += 1
  return home
    
        
for i in range(n):
  for j in range(n):
    if board[i][j] == 1 and not visited[i][j]:
      q.append((i, j))
      visited[i][j] = True
      homes_by_town.append(bfs())
      count += 1

print(count)
print(*homes_by_town.sorted())