[BOJ] 단지번호붙이기

---

코드

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

def bfs(i, j):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    q = deque()
    num = 0
    q.append((i, j))
    visited[i][j] = True

    while q:
        x, y = q.popleft()
        num += 1
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == 1 and not visited[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = True
                
    households.append(num)

n = int(input())
graph = []
visited = [[False]*n for _ in range(n)]
for _ in range(n):
    graph.append(list(map(int, list(input().rstrip()))))

apNum = 0
households = []
for i in range(n):
    for j in range(n):
        if not visited[i][j] and graph[i][j] == 1:
            bfs(i, j)
            apNum += 1

households.sort()
print(apNum)
print('\n'.join(map(str, households)))

결과

풀이 방법

• 흔한 그래프 탐색 문제이다. BFS를 활용하였다.
• 방문하지 않은 집(1)을 시작점으로 하여 BFS를 수행하며 단지 내 집의 수를 카운트한다. 한 번 방문한 집은 visited = True로 표시하여 다시 방문하지 않는다.

---