[백준] 1926번 그림

💡문제접근

• BFS 탐색 알고리즘을 이용해서 해결할 수 있었다. 상하좌우 탐색하여 만약 1이 이어져 있으면 면적을 1만큼 증가시키고 만약 탐색하는 과정에서 1이 나오면 그림이 존재하게 되므로 그림의 개수를 1만큼 증가시켜준다.

💡코드(메모리 : 35656KB, 시간 : 420ms)

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int, input().strip().split())
picture = [list(map(int, input().strip().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]

def BFS(x, y):
    area = 0
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True
    while queue:
        x, y = queue.popleft()
        dx = [0, 1, 0, -1]
        dy = [-1, 0, 1, 0]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if 0 <= nx < n and 0 <= ny < m and picture[nx][ny] == 1 and not visited[nx][ny]:
                area += 1
                visited[nx][ny] = True
                queue.append((nx, ny))
    return area + 1

cnt = 0
max_area = 0
for i in range(n):
    for j in range(m):
        if picture[i][j] == 1 and not visited[i][j]:
            cnt += 1
            max_area = max(max_area, BFS(i, j))
print(cnt)
print(max_area)

💡소요시간 : 10m