deque, heapq 사용하기 - 단지번호 붙이기

2667 단지번호 붙이기

import sys
from collections import deque
import heapq

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
q = deque()
heap = []

n = int(input())
board = [list(map(int, sys.stdin.readline().strip())) for _ in range(n)]
cnt = 0
vis = [[0] * n for _ in range(n)]

for i in range(n):
    for j in range(n):
        if board[i][j] == 1 and vis[i][j] == 0:
            size = 1
            cnt += 1
            q.append([i,j])
            vis[i][j] = 1
            while q:
                curX, curY = q.popleft()
                for dir in range(4):
                    nx = curX + dx[dir]
                    ny = curY + dy[dir]
                    if nx < 0 or nx >= n or ny < 0 or ny >= n:
                        continue
                    if board[nx][ny] == 0 or vis[nx][ny]:
                        continue
                    q.append([nx,ny])
                    vis[nx][ny] = 1
                    size += 1
            heapq.heappush(heap, size)
            
print(cnt)
for _ in range(cnt):
    print(heapq.heappop(heap))
                    
        
                    
                    
                    
                    
                    

📌 배운점

dequq 큐처럼 사용하기

queue = dequq()

queue.append([i,j])

queue.popleft()

heapq는 출력할 때 조심해야한다

for _ in range(cnt):
    print(heapq.heappop(heap))