[백준/Python] 1926 그림

문제

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

1926번: 그림

코드

def flood_fill():
    global val
    check[i][j]=val
    q.append((i,j))
    while q:
        x,y=q.popleft()
        for k in range(4):
            nx,ny=x+dx[k],y+dy[k]
            if 0 <=nx <n and 0 <= ny <m:
                if arr[nx][ny] and not check[nx][ny]:
                    check[nx][ny]=val
                    q.append((nx,ny))
    
from collections import deque
dx,dy=[-1,1,0,0],[0,0,-1,1]
n,m=map(int,input().split())
arr=[]
for _ in range(n):
    arr.append(list(map(int,input().split())))
check=[[0]*m for _ in range(n)]
val=1
q=deque()
for i in range(n):
    for j in range(m):
        if arr[i][j] == 1 and check[i][j] == 0:
            flood_fill()
            val+=1
            
print(val-1)

line=[0 for _ in range(val)]

for i in range(n):
    for j in range(m):
        if check[i][j] !=0:
            line[check[i][j]] += 1
if len(line)!=0:
    print(max(line))
else:
    print(0)

 

풀이

가로나 세로로 연결된 그림의 넓이를 찾기 위해 flood_fill()함수를 설정하여 val로 개수를 세고 list에 val만큼의 공간을 만들어서 세어진 val의 개수를 list 안에 넣어 그림의 넓이의 최댓값을 찾아 출력한다.