PS/Python
[백준] 2667 - 단지번호붙이기 (파이썬, Python)
w00se
2020. 7. 27. 21:57
https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. �
www.acmicpc.net
from collections import deque
import sys
def solution(i, j, cnt) :
cnt += 1
matrix[i][j] = 0
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
queue = deque([(i, j)])
while queue:
pos = queue.popleft()
for k in range(4):
cx = pos[0] + dx[k]
cy = pos[1] + dy[k]
if(0 <= cx and cx < N and 0 <= cy and cy < N):
if(matrix[cx][cy] != 0):
matrix[cx][cy] = 0
cnt += 1
queue.append((cx, cy))
return cnt
N = int(sys.stdin.readline().rstrip())
matrix = [[int(i) for i in sys.stdin.readline().rstrip()]for _ in range(N)]
dong = []
for i in range(N):
for j in range(N):
cnt = 0
if(matrix[i][j] != 0):
dong.append(solution(i, j, cnt))
print(len(dong))
dong.sort()
for i in dong:
print(i)