[Python - 1926] 그림 (S1)

문제

1926번: 그림

문제

문제 이해

• 도화지에 그려진 그림의 개수와 그림 중 넓이가 가장 넓은 그림의 넓이를 출력
• 1로 연결된 것을 한 그림이라고 정의, 가로나 세로는 연결된 것이고 대각선은 떨어진 것
• 그림의 넓이란 그림에 포함된 1의 개수

입력 조건

• 첫째 줄에 도화지의 세로 크기 n(1 <= n <= 500)과 가로 크기 m(1 <= m <= 500)이 주어짐
• 두 번째 줄부터 n+1 줄까지 그림의 정보가 주어짐 (0 : 색칠 안 된 부분, 1 : 색칠된 부분)

출력 조건

• 첫째 줄에는 그림의 개수, 둘째 줄에는 가장 넓은 그림의 넓이를 출력
• 단, 그림이 하나도 없는 경우에는 가장 넓은 그림의 넓이는 0

풀이

DFS를 사용해 도화지의 모든 부분을 순회하며, 그림의 개수와 가장 넓은 넓이를 탐색

1. 입력 조건에 맞게 n, m, graph(도화지) 입력
2. dfs 함수 구현 : count를 인자로 넣어 그림의 넓이를 확인
   • 도화지의 범위를 넘어가면 count 반환
   • 그림이 그려진 영역 (1)이면, 0으로 변경 후 가로/세로 영역을 재귀적으로 탐색
3. 모든 땅을 순회하며, 그림의 개수와 최대 넓이를 찾음

코드

• n과 m의 범위를 고려하여 recursion limit을 여유롭게 설정

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(x, y, count):
    if x < 0 or x >= n or y < 0 or y >= m:
        return count
    
    if graph[x][y] == 1:
        graph[x][y] = 0
        count += 1
        count = dfs(x + 1, y, count)
        count = dfs(x - 1, y, count)
        count = dfs(x, y + 1, count)
        count = dfs(x, y - 1, count)
        return count
    return count

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

max_area = 0
print_count = 0
for i in range(n):
    for j in range(m):
        area = dfs(i, j, 0)
        if area != 0:
            print_count += 1
        if max_area < area:
            max_area = area

print(print_count)
print(max_area)