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

🥚문제

---

🥚입력/출력

---

🍳코드

# 단지번호붙이기
from collections import deque
# 입력
n = int(input())
matrix = [[0]*(n+1)]
for i in range(n):
    matrix.append([0] + list(map(int, input())))

# bfs 함수
def bfs(x, y):
    queue = deque()
    queue.append((x, y)) # (x, y) 삽입
    matrix[x][y] = 0 # 방문 표시, 값을 0으로 바꿔줌
    house_count = 1 # 한 단지에 포함된 집 세기
    while queue:
        v = queue.popleft()
        x = v[0]
        y = v[1]
        # 인접 노드 삽입
        movs = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상 하 좌 우
        for mov in movs:
            nx = x + mov[0]
            ny = y + mov[1]
            # 유효 범위
            if 0 < nx < n+1 and 0 < ny < n + 1:
                if matrix[nx][ny] == 1:
                    queue.append((nx, ny)) # 삽입
                    matrix[nx][ny] = 0 # 방문 표시
                    house_count += 1
    return house_count

complex = [] # 단지 리스트
for i in range(1, n+1):
    for j in range(1, n+1):
        if matrix[i][j] == 1:
            complex.append(bfs(i, j))


# 총 단지 수
print(len(complex))
# 각 단지 내 집의 수를 오름차순으로
complex.sort()
for x in complex:
    print(x)

---

🧂아이디어

• matrix 순회하다가 1을 만나면 bfs 호출! bfs가 호출될 때 마다 새 단지가 꾸려진다고 이해하면 된다.

• bfs 내에서는 단지 안에 몇 개의 집이 있는지 세주고 그 수를 return 한다.