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

 

 

 

• bfs를 통해 bfs함수를 실행할 떄 마다 카운트를 올리며(단지 수) bfs함수 내에서는 집을 카운트하며(집의 수) 0으로 바꾸는 작업을 진행하였다.

 

from collections import deque

N = int(input())

arr=[list(map(int,input())) for _ in range(N)]
cnt = 0 # 단지의 수
result = [] # 각 단지의 집의 수를 담을 리스트

def bfs(y,x):
    q = deque([(y,x)])
    tmp = 1 
    arr[y][x] = 0

    while q:
        y,x = q.popleft()

        directy = [-1,1,0,0] # 상,하,좌,우로만 이동
        directx = [0,0,-1,1] 

        for k in range(4):
            dy = directy[k] + y
            dx = directx[k] + x

            if dy >= N or dy < 0 or dx >= N or dx < 0: # 목표 인덱스가 배열을 벗어난다면 continue
                continue
            if arr[dy][dx] == 1: 
                tmp += 1 # 상하좌우 내에 집이 있다면 임시변수에 +1
                arr[dy][dx] = 0
                q.append([dy,dx])
    result.append(tmp) # 단지의 집의 수를 result에 저장

for j in range(N):
    for i in range(N):
        if arr[j][i] == 1:
            cnt += 1 # 단지 수 카운트
            bfs(j,i)

print(cnt) # 단지 수 출력
result.sort()

for i in range(len(result)):
    print(result[i]) # 집의 수 출력