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

풀이

  1. 입력값을 homes 배열에 받고, 이 배열을 이중 반복문을 이용해 [0][0]부터 [n][n] 까지 검사한다.
  2. 만약 해당 값 (homes[i][j])가 1이라면 그 값을 queue에 넣고 이미 방문했다는 의미에서 1(VISITED로 상수처리)을 더한다.
  3. queue에서 가장 앞에 있는 값을 뽑고 그 값의 상하좌우 값을 is_there_neighbor 함수로 검사한다.
  4. 단지를 이룰 수 있는 집이면 이미 방문했다는 의미로 1을 더하고 queue에 넣는다. cnt도 1 추가한다.
  5. 이런 식으로 한 단지의 검사가 끝나면 지금까지 계산한 cnt를 answers에 append 하고 새로운 단지를 찾는다.

소스코드

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
homes = [[int(x) for x in input().strip()] for _ in range(n)]

def is_there_neighbor(x, y, homes):
    return 0 <= x < n and 0 <= y < n and homes[x][y] == 1

def bfs(homes, queue, answers):
    cnt = 1
    while queue:
        x, y = queue.popleft()
        
        DELTAS = ((1, 0), (-1, 0), (0, 1), (0, -1))
        for dx, dy in DELTAS:
            next_x, next_y = dx + x, dy + y
            if is_there_neighbor(next_x, next_y, homes):
                homes[next_x][next_y] += VISITED
                cnt += 1
                queue.append((next_x, next_y))

    answers.append(cnt)

queue = deque()
answers = []
VISITED = 1

for i in range(n):
    for j in range(n):
        if homes[i][j] == 1:
            queue.append((i, j))
            homes[i][j] += VISITED
            bfs(homes, queue, answers)

print(len(answers))

answers.sort()
for answer in answers:
    print(answer)