[백준/BFS] 1926번 그림

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

1926번: 그림

 

[풀이 과정]

 

원하는 답은 그림의 개수와, 가장 넓은 넓이를 구하는 것이다.

BFS (너비 우선 탐색)을 쓰면 된다.

 

import sys
from collections import deque

input = sys.stdin.readline
dx = [1,-1,0,0]
dy = [0,0,1,-1]

def find_draw(Map, q):
    global max_draw
    
    temp = 1

    while q:
        x, y = q.popleft()

        for i in range(4): //상하좌우 확인
            tx = x + dx[i]
            ty = y + dy[i]
            if 0<=tx<N and 0<=ty<M and Map[tx][ty] == 1: //인덱스 넘지 않고, 그림이 있으면
                temp += 1
                Map[tx][ty] = 0
                q.append((tx,ty))
                
    max_draw = max(temp,max_draw)

cnt = 0
max_draw = 0


N,M =map(int,input().split())
Map = [list(map(int,input().split())) for _ in range(N)]

for i in range(N):
    for j in range(M):
        if Map[i][j] == 1:
            q = deque([(i,j)])
            Map[i][j] = 0
            find_draw(Map,q)
            cnt += 1

print(cnt)
print(max_draw)