[백준] 2667번 단지번호 붙이기 파이썬

bled 2021. 6. 20. 11:48

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여

www.acmicpc.net

from collections import deque
def BFS(i, j):
    global matrix, cnt

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

    matrix[i][j] = 0
    count = 1
    while q:
        y, x = q.popleft()
        for i in range(4):

            nx = x + dx[i]
            ny = y + dy[i]

            if 0<=nx<N and 0<=ny<N and matrix[ny][nx]:
                q.append([ny, nx])
                matrix[ny][nx] = 0
                count += 1

    cnt.append(count)


N = int(input())
matrix = []
cnt = []
for i in range(N):
    matrix.append(list(map(int, input())))

for i in range(N):
    for j in range(N):
        if matrix[i][j] == 1:
            BFS(i,j)


print(len(cnt))
cnt.sort()
for c in cnt:
    print(c)