Question
문제링크
Silver 1
Logic
기본 구조 : bfs
1. 상하좌우를 탐색하기 위해 dx, dy를 선언한다.
2. 기본적으로 1로 표시되어있는 초기 그래프를 탐색하며, 1을 마주친다면 bfs를 실행시킨다.
3. 그래프의 범위 내에서, 1과 붙어있는 다음 1을 탐색하고, 갯수를 센다.
4. 이 과정을 모두 마치면, 각 단지 별 집의 수를 오름차순으로 출력한다.
Code
from collections import deque
dx = [-1,0,0,1]
dy = [0,1,-1,0]
def bfs(a,b):
global li
n=len(li)
queue = deque()
queue.append([a,b])
li[a][b] = 0
count=1
while queue:
x,y = queue.popleft()
for i in range(4):
xx = x+dx[i]
yy = y+dy[i]
if xx < 0 or xx >= n or yy < 0 or yy >= n: continue
if li[xx][yy] == 1:
li[xx][yy]=0
queue.append([xx,yy])
count+=1
return count
li=[]
N=int(input())
for _ in range(N):
li.append(list([int(i) for i in [*input()]]))
cnt=[]
for i in range(N):
for j in range(N):
if li[i][j]==1:
cnt.append(bfs(i,j))
cnt.sort()
print(len(cnt))
for _ in range(len(cnt)): print(cnt[_])