🪴 Quartz 4.0

BOJ 2667 - 단지번호붙이기

2 min read

풀이

입력받은 2차원 배열을 통 집이 있는 좌표에서 BFS 를 실행한다.

실행된 BFS 에서 인접한 집들이 있을 때 마다 houses 변수에 1을 더해준다.

더 이상 이어지는 집이 없을 경우 BFS 는 종료되고 houses 변수를 반환한다.

이 때 반환받은 houses 값을 ans 리스트에 저장해준 뒤 다음 집이 있는 장소에서 BFS 를 실행한다.

이 과정을 2차원 배열의 모든 요소에 대하여 실행하게 된 후 출력조건에 맞게 단지수와 각 단지에 있는 집의 개수를 출력하면 된다.

소스코드

# 단지번호붙이기
from collections import deque
import sys
input = sys.stdin.readline
 
def bfs(n, graph, i, j):
    q = deque()
    q.append([i, j])
    graph[i][j] = 0
    houses = 1
    while q:
        x, y = q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < n and 0 <= ny < n:  # 범위 내일 때
                if graph[nx][ny] == 1:  # 집이 이어져 있을 경우
                    q.append([nx, ny])
                    graph[nx][ny] = 0  # 방문 처리
                    houses += 1
    return houses
 
 
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
 
n = int(input())
graph = [list(map(int, input().rstrip())) for _ in range(n)]
ans = []
 
for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            ans.append(bfs(n, graph, i, j))
 
print(len(ans))
for a in sorted(ans):
    print(a)

References

Graph View