[BOJ] 백준 1926번 그림

백준 1926번 그림 (실버1)

문제

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

문제 풀이

간단한 BFS 문제이다.
BFS 함수를 돌리면서, 해당 좌표가 그림이라면 카운트를 해주고 이를 리턴하면 된다.
그리고 이러한 BFS 함수를 모든 좌표에 대하여 반복문을 돌린 이후 그림 개수와 최댓값을 출력하면 되겠다.

마지막 줄에 if count를 넣은 이유는, 만약 그림이 하나도 없을 시에 count 리스트는 빈 리스트가 되어 max(count)를 실행할 때 ValueError가 발생하기 때문이다.

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())

graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
visited = [[False for _ in range(m)] for _ in range(n)]


def bfs(x, y, visited):
    q = deque()
    q.append((x, y))
    dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
    cnt = 0
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and graph[nx][ny] == 1:
                visited[nx][ny] = True
                q.append((nx, ny))
                cnt += 1
    return cnt + 1


count = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1 and not visited[i][j]:
            visited[i][j] = True
            count.append(bfs(i, j, visited))

print(len(count))
if count:
    print(max(count))
else:
    print(0)