[백준] 1926번: 그림 - 파이썬

🔈 문제

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

 

 

📝입력

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

 

📑출력

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

 

📚 문제 해석

쉽게 해석하면 그래프가 주어졌을 때 연결되어 있는 요소의 갯수와 연결되어 있는 요소의 최대값을 구하면 되는 문제이다. BFS 를 사용하여 DFS 보다 빠른 풀이가 가능하다.

 

📖 풀이

다른 BFS 문제들처럼 색칠되어 있는 부분을 찾아 방문하고 BFS 탐색을 시작한다. 이때 연결 요소의 최대값(그림의 넓이)를 출력해주기 위해 are 라는 변수에 연결 수를 담고 res 배열에 담아주었다. 체크해야 할 것은 그림이 하나도 그려지지 않을 경우 0을 출력해야하는데 max 함수는 빈 배열에서 작동하지 않는다. 이부분을 if 문을 사용하여 처리할 수도 있지만, 필자는(으악 오글거림) res 배열 생성할 때 0을 넣음으로써 해결하였다. 시간면에서는 별차이 없어보이지만 코드가 더 예뻐보인다.

 

💻 코드

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

n,m = map(int,input().rstrip().split())
do = [] # 도화지, 그래프
cnt = 0 # 그림의 갯수 변수
res = [0] # 그림의 넓이 담을 배열

# 그림 그리기
for i in range(n):
    do.append(list(map(int,input().rstrip().split())))
    
def bfs(x,y):
	# 상하좌우 4방향
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    queue = deque()
    queue.append([x,y])
    do[x][y] = 0 # 시작점 방문처리
    are = 1 # 넓이는 1부터 시작
    while queue:
        a,b = queue.popleft()
        for i in range(4):
            nx = a + dx[i]
            ny = b + dy[i]
			# 도화지 안에 위치하고 아직 방문하지 않았다면 방문
            if 0 <= nx < n and 0 <= ny < m and do[nx][ny] == 1:
                are += 1 # 넓이 키우기
                do[nx][ny] = 0 # 방문 처리            
                queue.append([nx, ny]) # 큐에 삽입
    res.append(are) # 그림의 넓이 배열에 삽입

for x in range(n):
    for y in range(m):
        if do[x][y] == 1: # 그림이 그려져있다면 BFS 탐색 시작
            bfs(x,y)
            cnt += 1 # 그림 갯수 +1

print(cnt) # 그림갯수 출력
print(max(res)) # 그림의 넓이 최대값 출력

 

🔗 문제링크 : 그림

1926번: 그림