[10/18] 2667 (단지번호붙이기)

실버1 문제
BFS

내 코드

from collections import deque

n = int(input())
arr = []
for _ in range(n):
    temp = list(map(int, input()))
    arr.append(temp)
    
# 단지 수
village = 2
# 집의 수 리스트
house = []

move_h = [1, -1, 0, 0]
move_w = [0, 0, 1, -1]
    
def bfs(h, w):
    global village
    
    cnt = 0
    queue = deque()
    queue.append([h, w])
    
    arr[h][w] = village
    cnt += 1
    
    while queue:
        hh, ww = queue.popleft()
        
        for i in range(4):
            temp_h = hh + move_h[i]
            temp_w = ww + move_w[i]
            
            # 맵 밖으로 나갔는지 확인
            if ( temp_h < 0 or temp_h >= n or temp_w < 0 or temp_w >= n ):
                continue
                        
            # 1인지 확인
            if ( arr[temp_h][temp_w] != 1 ):
                continue
            
            # 1을 village로 바꿔줌
            cnt += 1
            arr[temp_h][temp_w] = village
            queue.append([temp_h, temp_w])
    
    # 다 끝났으면 단지 번호 늘려줌
    village += 1
    house.append(cnt)
    
for i in range(n):
    for j in range(n):
        if arr[i][j] == 1:
            bfs(i, j)
            
print(village - 2)
house.sort()
for i in house:
    print(i)

로직

• BFS

피드백

• 집이 하나만 있는 단지를 고려하지 않고 구현했었다.
• 처음 함수에 들어간 좌표도, while문에 들어가기 전에 cnt와 좌표를 바꿔준다.