[백준_16932] 모양만들기 python

https://www.acmicpc.net/problem/16932

16932번: 모양 만들기

문제 해결

• 문제 : 1이 들어있는 칸을 연결한 것을 모양이라 부른다. 배열 칸 하나의 수를 변경해서 만들 수 있는 모양의 최대 크기를 구하자
  • 1을 변경하면 모양에 변화가 없으니 0을 변화시켜야 함을 알 수 있다.
  • 배열의 한 칸의 수를 변경하여 만들 수 있는 모양의 최대 크기에서 0의 칸을 하나 변경시켜 인접한(상하좌우) 곳을 살펴서
  • 서로 다른 영역의 크기의 합 + 1(현재칸)의 최댓값을 구해준다.
• 서로다른 영역을 구별해야 하기 때문에 각 영역마다 id값을 부여한다(저는 visited값을 1부터 방문 처리하여 각기 다른 숫자로 영역을 구분했습니다.)
• 그 영역의 크기에 맞는 값의 합을 answer에 최댓값으로 초기화시켜준다.
•  

from collections import deque

n,m = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
visited = [[0]*m for _ in range(n)]
dxs, dys = [0,0,1,-1],[1,-1,0,0]
dic = dict()

def in_range(x,y):
    return 0<=x<n and 0<=y<m

def bfs(x,y,cnt):
    visited[x][y] = cnt
    que = deque()
    que.append((x,y))
    while que:
        dx,dy = que.popleft()
        for i in range(4):
            nx,ny = dx+dxs[i], dy+dys[i],
            if in_range(nx,ny) and not visited[nx][ny] and graph[nx][ny]:
                visited[nx][ny] = cnt
                que.append((nx,ny))

#visited의 숫자에따라 영역 구별하기
cnt = 0
for i in range(n):
    for j in range(m):
        if graph[i][j] and not visited[i][j]:
            cnt += 1
            bfs(i,j,cnt)

#dic에 영역별(key)로 영역의 크기(value)를 저장
for i in range(n):
    for j in range(m):
        if visited[i][j] > 0:
            if not visited[i][j] in dic:
                dic[visited[i][j]] = 1
            else:
                dic[visited[i][j]] += 1

#그래프의 0인부분만 보고 상하좌우를 체크, 영역별 최대크기를 초기화해준다. 
answer = 0
for i in range(n):
    for j in range(m):
        if graph[i][j]==0: #그래프 0위치에서 상하좌우
            brr= []
            for t in range(4):
                nx,ny = i+dxs[t], j+dys[t]
                if in_range(nx,ny) and visited[nx][ny]:
                    brr.append(visited[nx][ny])
            res = 0
            for k in (set(brr)):
                res += dic[k]
            answer = max(answer,res+1)

print(answer)