이 문제를 보고 입력창을 보자마자 이건 BFS로 풀어야 되겠다는 생각이 바로 들었다.
Queue 배열에 들어갈 때 마다 영역의 넓이를 하나씩 늘리는 방법으로 풀면 생각보다 쉽게 풀 수 있다.
처음부터 끝까지 다 돌면서 아직 돌지 않은 영역을 BFS의 시작 지점으로 만들어서 전부 탐색할 수 있게 만들었다.
from collections import deque
def bfs(graph, start):
dx = [-1,1,0,0]
dy = [0,0,-1,1]
queue = deque()
queue.append(start)
area = 0
isnothing = True
while queue:
x,y = queue.popleft()
for i in range(len(dx)):
nx = x+dx[i]
ny = y+dy[i]
if nx>high-1 or ny>width-1 or nx<0 or ny<0 :
continue
if graph[nx][ny]==1:
queue.append((nx,ny))
area = area + 1
graph[nx][ny] = graph[x][y]+1
isnothing = False
if isnothing:
return area + 1
return area
high, width = map(int, input().split(' '))
count = 0
graph = []
for i in range(high):
graph.append(list(map(int,input().split(' '))))
area = []
for i in range(width):
for j in range(high):
if(graph[j][i] == 1):
area.append(bfs(graph,[j,i]))
count = count + 1
print(count)
if(len(area)==0):
print(0)
else:
print(max(area))마지막에는 bfs가 들어가지 않을 때를 예외처리하기 위한 코드이다.
