알고리즘
백준 1926번 : 그림(python)
jenyy
2021. 1. 5. 20:42
https://www.acmicpc.net/problem/1926
1926번: 그림
어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로
www.acmicpc.net
n,m = map(int, input().split())
data = [list(map(int,input().split())) for _ in range(n)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs(x,y):
w = 1
queue = [(x,y)]
while queue:
x,y = queue.pop()
for i in range(4):
nx,ny = x+dx[i],y+dy[i]
if 0<=nx<n and 0<=ny<m:
if data[nx][ny] == 1 and not check[nx][ny]:
w += 1
check[nx][ny] = 1
queue.append((nx,ny))
return w
cnt,wide = 0,0
check = [[0]*m for _ in range(n)]
for i in range(n):
for j in range(m):
if data[i][j]==1 and not check[i][j]:
cnt += 1
check[i][j] = 1
wide = max(wide, bfs(i,j))
print(cnt)
print(wide)