백준 1926번. 그림 (Python / 파이썬)

문제

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

입력

첫째 줄에 도화지의 세로 크기 n(1 ≤ n ≤ 500)과 가로 크기 m(1 ≤ m ≤ 500)이 차례로 주어진다. 두 번째 줄부터 n+1 줄 까지 그림의 정보가 주어진다. (단 그림의 정보는 0과 1이 공백을 두고 주어지며, 0은 색칠이 안된 부분, 1은 색칠이 된 부분을 의미한다)

출력

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

---

문제 풀이

가로나 세로로 연결된 1이 있을 때 그림이라고 판단합니다.

따라서 1이 있을 때 상,하,좌,우를 탐색하면 되므로

DFS 알고리즘을 이용했습니다.

 

각 도화지의 위치에서 탐색을 수행해주었습니다.

만약 범위를 벗어나면 False를 반환하고

도화지의 값이 1이라면 방문했음을 표시하기 위해 0으로 만든 뒤

상, 하, 좌, 우로 탐색해줍니다. 

이때 도화지의 값이 1일 때마다 넓이를 구하기 위해 count를 세어줍니다.

만약 탐색을 모두 수행했다면 True를 반환합니다.

 

만약 반환된 값이 True라면 그림을 찾은 것이므로 

그림의 개수를 세어주고 구한 count 중 최댓값을 찾아줍니다.

---

import sys
sys.setrecursionlimit(1000000)

def dfs(x, y):
    global count

    if x < 0 or x >= n or y < 0 or y >= m: # 범위를 벗어나면 False
        return False
     
    if paint[x][y] == 1: # 1이라면
        paint[x][y] = 0  # 방문했음을 표시하기 위해 0으로
        count += 1       # 넓이 증가시켜줌
        # 상,하,좌,우 탐색
        dfs(x - 1, y)
        dfs(x + 1, y)
        dfs(x, y - 1)
        dfs(x, y + 1)
        return True    # 탐색 완료하면 True
    
    return False

n, m = map(int,input().split()) # 도화지 세로 가로 크기

paint = []
for _ in range(n):
    paint.append(list(map(int,input().split()))) # 도화지 정보

result = 0
max_value = -1e9
for i in range(n):
    for j in range(m):
        count = 0
        if dfs(i, j):   # 그림을 찾았으면
            result += 1 # 개수 세어줌
        max_value = max(max_value, count) # 그림의 넓이 중 최댓값 계산

print(result)
print(max_value)