백준 2667 단지번호붙이기

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

2667번: 단지번호붙이기

 

흔한 탐색문제

bfs로풀음

2차원 배열 apartment를 돌면서,

만약 apartment[i][j[]가 '1'인 경우에 bfs를 실행한다.

여기서 한번에 몇집이나 탐색하는지만 세어주면 된다.

 

 

##코드##

import sys
input=sys.stdin.readline
from collections import deque
#bfs
moves=[[-1,0],[1,0],[0,-1],[0,1]]
def bfs(i,j):
    s=deque()
    s.append([i,j])
    apartment[i][j]=0
    cnt=1
    while s:
        i,j=s.popleft()
        for move in moves:
            a,b=move
            tmp_i,tmp_j=i+a,j+b
            # print(tmp_i,tmp_j)
            if (0<=tmp_i<n)and(0<=tmp_j<n)and(apartment[tmp_i][tmp_j]=='1'):
                
                s.append([tmp_i,tmp_j])
                apartment[tmp_i][tmp_j]='0'
                cnt+=1

    return cnt
        
    


n=int(input())
apartment=[list(input())for _ in range(n)]

l=[]
for i in range(n):
    for j in range(n):
        if apartment[i][j]!='0':
            l.append(bfs(i,j))
l.sort()
print(len(l))
for ll in l:
    print(ll)