[백준] 모양 만들기

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

16932번: 모양 만들기

Flood Fill을 활용하여 풀이하였습니다. 각각의 그룹을 기록해주고 해당 그룹과 연결될 수 있는 빈칸들에 현재 그룹들을 set에 넣어줍니다. 그 다음 2차원 배열을 돌면서 현재가 빈칸이고 다른 그룹에 연결될 수 있는 후보 그룹들이 set에 저장되어 있으므로 해당 set에 저장되어 있는 후보 그룹들의 면적을 더해주면 현재 칸을 변경했을 때 얻을 수 있는 모양의 최대 크기가 됩니다.

 

import sys
from collections import deque

#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n, m = tuple(map(int, input().split()))

board = [
    list(map(int, input().split()))
    for _ in range(n)
]

visited = [
    [False] * m
    for _ in range(n)
]

attached = [
    [set()
    for __ in range(m)]
    for _ in range(n)
]
group = 1

area = [0] * (1000 * 1000 + 3)

dys = [0, 1, 0, -1]
dxs = [1, 0, -1, 0]

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

def bfs(startY, startX):
    global group
    q = deque([(startY, startX)])

    visited[startY][startX] = True
    cnt = 0

    while q:
        y, x = q.popleft()
        cnt += 1

        for dy, dx in zip(dys, dxs):
            ny = y + dy
            nx = x + dx

            if inRange(ny, nx) and not visited[ny][nx]:
                # 빈 공간이면 해당 그룹을 넣어준다.
                if board[ny][nx] == 0:
                    attached[ny][nx].add(group)
                # 1이면 ff해준다.
                else:
                    visited[ny][nx] = True
                    q.append((ny, nx))

    area[group] = cnt

for i in range(n):
    for j in range(m):
        if board[i][j] == 1 and not visited[i][j]:
            bfs(i, j)
            group += 1

maxCnt = 1

for i in range(n):
    for j in range(m):
        if board[i][j] == 0:
            sumOfArea = sum([
                area[x] for x in attached[i][j]
            ])

            maxCnt = max(maxCnt, sumOfArea)

print(maxCnt + 1)