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

yewon Lee·2023년 5월 16일
0


BACKJOON>2667번:단지번호 붙이기


📘문제풀이

from collections import deque

n = int(input())
mapList = [list(map(int, input())) for _ in range(n)]
visited= [[False] * n for _ in range(n)]

bn = [] #각단지내 집 수
c = 0 #총 단지 수

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

queue = deque()

def bfs(cx, cy, graph, visited):
    b = 1
    queue.append((cx, cy))
    visited[cx][cy] = True     
    while queue:
        px, py = queue.popleft()
        for i in range(4):
            nx = px + dx[i]
            ny = py + dy[i]
            if nx <= -1 or nx >= n or ny <= -1 or ny >= n:
                continue
            if visited[nx][ny] != True and mapList[nx][ny] != 0:
                queue.append((nx,ny))
                visited[nx][ny] = True
                b += 1
                mapList[nx][ny] = mapList[px][py] + 1
                
    bn.append(b)

for i in range(n):
    for j in range(n):
        if mapList[i][j] == 1:
            cx = i
            cy = j
            bfs(cx, cy, mapList, visited)
            c += 1

print(c)
bn.sort()
for i in range(len(bn)):
    print(bn[i])
profile
시작

0개의 댓글