[백준] [Python] 2667번 단지번호붙이기 - BFS - [대표예제]

 

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

 

Python

import sys

row = col = int(sys.stdin.readline().rstrip())
board =[ list(map(int, list(sys.stdin.readline().rstrip()))) for _ in range(row) ]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
visit = [[0 for _ in range(col)] for _ in range(row)]
q = []
cnt = 0
area = []
for a in range(row):
    for b in range(col):
        if board[a][b] == 1 and visit[a][b] == 0:
            visit[a][b] = 1
            q.append((a,b))
        
            temp_area = 1
            while (len(q) != 0):
                #print(q)
                pos = q.pop(0)
            
                for i in range(4):
                    nx = pos[0] + dx[i]
                    ny = pos[1] + dy[i]
                    if (0<=nx<row and 0<=ny<col):
                        if (visit[nx][ny] == 0 and board[nx][ny] == 1):
                            visit[nx][ny] = visit[pos[0]][pos[1]]+1
                            temp_area+=1
                            q.append((nx,ny))
                #print(i,visit)
            cnt += 1
        
            area.append(temp_area)
print(cnt)
area.sort()
for x in area:
    print(x)