이번 문제는 BFS를 통해 해결하였다. 모든 0을 1로 바꾼 모든 경우에 대하여 BFS 탐색을 진행하였고, 시간초과가 발생하였다. 그래서 다른 방법에 대해 생각해보았고, BFS를 통해 기존의 1의 그룹을 저장하고, 0을 탐색하며 상하좌우에 있는 그룹의 크기의 합 중 가장 큰 값을 결과값으로 취하는 방법으로 접근하였다. 이를 위해 0의 좌표를 zeros 리스트에 담았고, 1의 좌표를 ones 리스트에 담았다.

Code

처음 제출 코드 (시간초과)

from collections import deque
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
zeros = []
ones = []
for i in range(n):
    for j in range(m):
        if grid[i][j] == 0:
            zeros.append((i, j))
        if grid[i][j] == 1:
            ones.append((i, j))
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
def find_ones(y, x):
    q = deque()
    q.append((y, x))
    visited[y][x] = True
    result = 1
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < m and grid[ny][nx] == 1 and not visited[ny][nx]:
                visited[ny][nx] = True
                result += 1
                q.append((ny, nx))
    return result
answer = 0
for zy, zx in zeros:
    visited = [[False for _ in range(m)] for _ in range(n)]
    answer = max(answer, find_ones(zy, zx))
    for y, x in ones:
        if not visited[y][x]:
            answer = max(answer, find_ones(y, x))
print(answer)

정답 코드

from collections import deque
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
zeros = []
ones = []
for i in range(n):
    for j in range(m):
        if grid[i][j] == 0:
            zeros.append((i, j))
        if grid[i][j] == 1:
            ones.append((i, j))
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
visited = [[False for _ in range(m)] for _ in range(n)]
answer = 0
num = 1
groups = [0 for _ in range(n*m+1)]
def find_group(y, x):
    q = deque()
    q.append((y, x))
    visited[y][x] = True
    path = [(y, x)]
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < m and grid[ny][nx] == 1 and not visited[ny][nx]:
                visited[ny][nx] = True
                path.append((ny, nx))
                q.append((ny, nx))
    for y, x in path:
        grid[y][x] = num
    groups[num] = len(path)
for y, x in ones:
    if not visited[y][x]:
        find_group(y, x)
        num += 1
for y, x in zeros:
    result = 1
    near = []
    for i in range(4):
        ny, nx = y+dy[i], x+dx[i]
        if 0 <= ny < n and 0 <= nx < m:
            if grid[ny][nx] not in set(near):
                near.append(grid[ny][nx])
                result += groups[grid[ny][nx]]
    answer = max(answer, result)
print(answer)