백준 2667 단지번호붙이기

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

2667번: 단지번호붙이기<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여www.acmicpc.net

흔한 탐색문제

bfs로풀음

2차원 배열 apartment를 돌면서,

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

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

##코드##

import sysinput=sys.stdin.readlinefrom 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)