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

 

 

" 백준 1926번 그림 문제 파이썬 "

 

 

 

" 💡 문제 해결 아이디어 "

 

1926번 그림 문제는 0과 1로 이루어진 그래프에서 상하좌우가 1로 연결된 그림을 찾아 그 갯수와 그 그림들 중 가장 넓은 넓이를 출력하는 문제이다.

 

for문을 통해 그래프의 0,0 ~ n-1,m-1 까지 전체를 탐색하며 값이 1인 지점을 찾을 때마다 cnt +=1 을 한다.

그리고 값이 1인 지점의 x,y좌표를 bfs로 탐색하여 그 지점에 연결되어 있는 1들을 모두 0으로 변경하며 1이 0으로 변경되는 횟수를 area(넓이) 변수에 +1 해주고 더이상 연결된 1이 없다면 area 변수의 값을 return한다.

 

return받은 area변수는 이전에 서칭한 가장 넓었던 그림의 면적(maxArea 변수)와 비교하여 더 큰 값을 다시 maxArea 변수에 저장한다.

 

 

 

코드

from collections import deque

def bfs(x,y):
    area = 1
    queue = deque([(x,y)])
    graph[x][y] = 0
    while queue:
        a,b = queue.popleft()
        for i in range(4):
            nx,ny = a+dx[i],b+dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == 1:
                area+=1
                queue.append((nx,ny))
                graph[nx][ny] = 0
    return area

n,m = map(int,input().split())
graph = []

dx,dy = [-1,1,0,0],[0,0,-1,1]

for _ in range(n):
    graph.append(list(map(int,input().split())))

cnt = 0
maxArea = 0

for i in range(n):
    for j in range(m):
        if graph[i][j] == 1:
            cnt+=1
            maxArea = max(bfs(i,j), maxArea)

print(cnt)
print(maxArea)