백준 / python / 16932. 모양 만들기

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

 

문제 요약

0과 1로 구성된 격자가 주어진다.

1 끼리 상하좌우 중 하나로 이동하여 서로 도달할 수 있으면 연결된 격자라고 한다.

서로 연결된 격자들을 같은 모임에 넣었을 때, 가장 많은 격자를 가지고 있는 모임의 총 격자 수를 구하라.

단, 0 하나를 1로 바꿀 수 있다.

 

 

풀이 요약

1. 0을 1로 바꾸고 전수 검사를 하는 방식으로는 $O(N^2 * (V + E)) = O(N^3) $ 의 시간복잡도를 가지므로 $N=1000$ 에서 시간초과가 발생한다.
2. 따라서 연결된 격자들의 모임에 포함된 총 격자의 수를 미리 구하고 0 만을 순회하며 인근의 총 격자 수를 더해준다.

 

주의사항

1. BFS 문제를 풀 때 항상 큐에 같은 값이 담기지 않도록 하는 것이 중요하다.
   이를 위해 큐에 새로운 항목을 삽입할 때, `visited` 배열을  갱신해야한다.

 

from sys import stdin
from collections import deque

input = stdin.readline

memory = [0]
graph = []
zeros = []
moves = [
    (0, 1),
    (0, -1),
    (1, 0),
    (-1, 0),
]
N, M = map(int, input().split())
visited = [False] * (N * M)

for n in range(N):
    row = list(map(int, input().split()))
    graph.append(row)
    for m in range(M):
        if not row[m]:
            zeros.append((n, m))


def bfs(pos, key):
    y, x = pos
    q = deque([pos])
    memory.append(1)
    visited[y * M + x] = True
    graph[y][x] = key

    while q:
        y, x = q.popleft()

        for dy, dx in moves:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < N and 0 <= nx < M:
                if not visited[ny * M + nx] and graph[ny][nx]:
                    q.append((ny, nx))
                    memory[key] += 1
                    visited[ny * M + nx] = True
                    graph[ny][nx] = key


for n in range(N):
    for m in range(M):
        if not visited[n * M + m] and graph[n][m]:
            bfs((n, m), len(memory))

max_answer_score = 0
for y, x in zeros:
    answer = set()
    for dy, dx in moves:
        ny = y + dy
        nx = x + dx
        if 0 <= ny < N and 0 <= nx < M:
            answer.add(graph[ny][nx])
    answer_score = sum([memory[key] for key in answer])

    if max_answer_score < answer_score:
        max_answer_score = answer_score

print(max_answer_score + 1)