from collections import deque
N = int(input())
graph = []
graph.append([0 for _ in range(N+2)])
for _ in range(N):
t = input()
tt = [0]
for i in range(N):
tt.append(int(t[i]))
tt.append(0)
graph.append(tt)
graph.append([0 for _ in range(N+2)])
def bfs(graph, a, b):
queue = deque([[a, b]])
graph[a][b] = 0
ans = 1
while queue:
v = queue.popleft()
p = v[0]
q = v[1]
for i in range(p-1, p+2):
for j in range(q-1, q+2):
if i+j == p+q-1 or i+j == p+q+1:
if graph[i][j] == 1:
queue.append([i, j])
graph[i][j] = 0
ans += 1
return ans
answer = []
for i in range(1, N+1):
for j in range(1, N+1):
if graph[i][j] == 1:
answer.append(bfs(graph, i, j))
print(len(answer))
for x in sorted(answer):
print(x)queue를 이용해 BFS로 풀었습니다.
graph를 탐색할 때, 첫 번째 행의 요소를 기준으로 위쪽의 점을 탐색하지 못합니다.
마찬가지로, 첫 번째 열의 요소를 기준으로는 왼쪽의 점을 탐색하지 못합니다.
이러한 것들에 조건을 붙여주지 않고 1행, 1열, 마지막 행, 마지막 열을 0(집이 없는 곳)으로 덮고 시작했습니다.
예를 들어, 기존 graph가 [[1, 0, 1], [1, 0, 1], [0, 0, 1]]이라면 제가 만든 graph는 [[0, 0, 0, 0, 0], [0, 1, 0, 1, 0], [0, 1, 0, 1, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0]]입니다.
이렇게 풀면 조금 더 편하게 풀 수 있을 것이라고 생각했습니다.
