[알고리즘] 백준 1926 파이썬 - 그림

 

1926번: 그림

문제

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

 

문제풀이

from collections import deque
n,m=map(int,input().split())
graph=[]
for _ in range(n):
    graph.append(list(map(int,input().split())))

def bfs(x,y):
	#01
    q=deque([(x,y)])
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    graph[x][y]=0
    cnt=1
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            #02
            if 0<=nx<n and 0<=ny<m and graph[nx][ny]==1:
                graph[nx][ny]=0
                cnt+=1
                q.append((nx,ny))
    return cnt
ans=[]
for i in range(n):
    for j in range(m):
    	#03
        if graph[i][j]:
            ans.append(bfs(i,j))
#04
if len(ans)==0:
    print(len(ans))
    print(0)
else:
    print(len(ans))
    print(max(ans))

- #01 : dx,dy를 통해 움직일 수 있는 좌표값을 지정한다. 

           #03에 의해 bfs가 실행될 때는 graph[x][y] 값이 1이기에,

          graph[x][y] 값을 0으로 바꿔주고 cnt는 1부터 시작한다.

- #02 : nx,ny라는 움직인 후의 좌표가 조건을 만족하면, graph 값을 0으로 바꿔주고

           cnt를 1늘려주고 q에 추가해준다. 참고로 cnt는 그림의 넓이를 뜻한다.

           이후 끝나면 cnt를 반환해준다.

- #03 : graph[i][j]가 1일 때 bfs를 실행한 결과값을 ans에 추가한다.

           즉 각각의 그림의 넓이를 ans에 추가하는 것이다.

- #04 : ans 즉 그림이 없으면 0,0을 출력하고,

           그림이 있으면 ans의 길이와 제일 큰 값을 출력한다.