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

💡문제접근

• BFS알고리즘을 이용했다. 만약 탐색하고자하는 위치의 값이 1이라면 BFS를 실행한다. 상하좌우 탐색을 통해서 조건을 만족시키면 계속 탐색을 수행해나가면서 단지에 속하는 집의 수를 1씩 더해준다. 만약 큐가 비어있다면 탐색을 중지하고 단지에 속하는 집의 수를 return해준다.

💡코드(메모리 : 34184KB, 시간 : 68ms)

from collections import deque

import sys
input = sys.stdin.readline

N = int(input().strip())
apartment = [list(map(int, input().strip())) for _ in range(N)]
cnt = 0

def BFS(graph, x, y):
    queue = deque()
    queue.append([x, y])
    # 집이 있는 곳을 방문한다면 그 위치의 값을 0으로 초기화
    graph[a][b] = 0
    # 단지에 속하는 집의 수를 1만큼 증가
    cnt = 1
    while queue:
        x, y = queue.popleft()
        dx = [0, 1, 0, -1]
        dy = [-1, 0, 1, 0]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] == 1:
                cnt += 1
                graph[nx][ny] = 0
                queue.append([nx, ny])
    return cnt

arr = []
for a in range(N):
    for b in range(N):
        if apartment[a][b] == 1:
            arr.append(BFS(apartment, a, b))
            cnt = 0

arr.sort()
print(len(arr))
for i in arr:
    print(i)

💡소요시간 : 31m