[BOJ] 1926. 그림

📌 문제 제목

문제 링크: BOJ 1926

---

🗒️ 문제 설명

어떤 도화지에 그림이 그려져 있을 때, 그 그림의 개수와 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라.

단, 그림이라는 것은 1로 연결된 것을 그림이라고 정의한다.

시간 제한: 2초

메모리 제한: 128MB

세로 크기: 1 <= n <= 500

가로 크기: 1 <= m <= 500

---

💡 문제 해결 아이디어

• NM이 250,000 이므로 O(NM)의 시간복잡도를 가진 알고리즘을 사용하면 해결 가능.
• 이차원 배열을 순회하며 그림의 시작점을 찾고 BFS로 그림의 개수와 넓이를 구한다.
• 그림의 개수는 이차원 배열을 돌며 BFS를 수행할 때마다 count를 증가시킨다.
• 그림의 넓이는 BFS의 리턴값을 해당 그림의 넓이로 하고, BFS가 끝나면 해당 그림의 넓이와 이전에 저장해둔 그림의 최대 넓이를 비교한다.

---

⌛️ 시간 복잡도

• O(NM)

---

✅ 최종 코드

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

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

visited = [[False] * M for _ in range(N)]
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def bfs(graph, x, y, visited) -> int:
    queue = deque([(x, y)])
    visited[x][y] = True
    area = 1
    while queue:
        xp, yp = queue.popleft()
        for dx, dy in direction:
            nx, ny = xp + dx, yp + dy
            if not (0 <= nx < N and 0 <= ny < M):
                continue
            if not visited[nx][ny] and graph[nx][ny] == 1:
                queue.append((nx, ny))
                visited[nx][ny] = True
                area += 1
    return area


count = 0
mx = 0
for i in range(N):
    for j in range(M):
        if not visited[i][j] and graph[i][j] == 1:
            count += 1
            area = bfs(graph, i, j, visited)
            mx = max(mx, area)

print(count)
print(mx)