[ BOJ ] 16932 : 모양 만들기 ( GOLD 3 ) / Python

문제

N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다.

1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의 연결 요소를 모양이라고 부르자. 모양의 크기는 모양에 포함되어 있는 1의 개수이다.

배열의 칸 하나에 들어있는 수를 변경해서 만들 수 있는 모양의 최대 크기를 구해보자.

입력

첫째 줄에 배열의 크기 N과 M이 주어진다. 둘째 줄부터 N개의 줄에는 배열에 들어있는 수가 주어진다.

출력

첫째 줄에 수 하나를 변경해서 만들 수 있는 모양의 최대 크기를 출력한다.

제한

• 2 ≤ N, M ≤ 1,000
• 0과 1의 개수는 하나 이상이다.

풀이 과정

먼저 이미 있는 1의 모양을 먼저 탐색하면서 방문 기록을 이용해 모양의 크기를 기록하고, 모양이 몇 번째 그룹인지 기록한다. 전체 배열에서 0을 탐색하면서, 해당 위치의 0을 1로 변경했을 때 인접한 1의 모양과 연결해 크기를 합산하여 계산한다. 인접한 네 개의 면 중에서 같은 그룹의 1이 있을 수 있으니 이 중복을 고려한다. 

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

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

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

visit = [[0 for j in range(m)] for i in range(n)]

group = 1
groups = {}

row = [-1,1,0,0]
col = [0,0,-1,1]

for i in range(n):
    for j in range(m):
        if maps[i][j] == 1 and visit[i][j] == 0:
            visit[i][j] = group
            cnt = 0
            
            q = deque()
            q.append([i, j])
            while q:
                size = len(q)

                for s in range(size):
                    cnt += 1
                    y = q[0][0]
                    x = q[0][1]
                    q.popleft()
                    for d in range(4):
                        ny = y + row[d]
                        nx = x + col[d]

                        if 0 <= ny < n and 0 <= nx < m and maps[ny][nx] == 1 and visit[ny][nx] == 0:
                            q.append([ny, nx])
                            visit[ny][nx] = group

            groups[group] = cnt
            group += 1

max_size = 1

for i in range(n):
    for j in range(m):
        if maps[i][j] == 0:
            group_in = {}
            now_size = 1
            for d in range(4):
                ny = i + row[d]
                nx = j + col[d]

                if 0 <= ny < n and 0 <= nx < m and maps[ny][nx] == 1 and group_in.get(visit[ny][nx], -1) == -1:
                    group_in[visit[ny][nx]] = 1
                    now_size += groups[visit[ny][nx]]
            
            max_size = max(max_size, now_size)

print(max_size)