[Python/파이썬] 백준 16932번 모양 만들기

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

코드

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

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

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def bfs(x, y, group_num):
    res = 1
    q = deque([(x, y)])
    matrix[x][y] = group_num
    while q:
        now_x, now_y = q.popleft()
        for i in range(4):
            nx = now_x+dx[i]
            ny = now_y+dy[i]
            if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] == 1:
                q.append((nx, ny))
                matrix[nx][ny] = group_num
                res += 1
    return res


group_num = 2
group = dict()
for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1:
            size = bfs(i, j, group_num)
            group[group_num] = size
            group_num += 1

answer = 0
for x in range(n):
    for y in range(m):
        if matrix[x][y] == 0:
            cnt = 1
            visited_group = set([0])
            for d in range(4):
                nx = x+dx[d]
                ny = y+dy[d]
                if 0 <= nx < n and 0 <= ny < m and matrix[nx][ny] not in visited_group:
                    group_num = matrix[nx][ny]
                    cnt += group[group_num]
                    visited_group.add(group_num)
            answer = max(answer, cnt)
print(answer)

 

 

BFS 활용해서 해야 하는건 감을 잡았는데, 처음에는 한 번의 탐색만으로 정답을 구할 수 있지 않을까? 했는데, 이건 BFS로는 방법이 없어보여서 포기하고 방향을 틀었다.

 

위에서 작성한 코드는 다음과 같은 방법으로 실행된다.

1. 일단 배열의 모든 칸을 순회하며 1인 칸에서 `bfs` 함수를 실행해서 그룹을 표시해둔다. 같은 그룹에 속한 칸은 모두 같은 수로 표시된다. 이때 bfs를 실행하며 각 그룹의 사이즈(칸 수)도 구해서 저장해둔다.

ex.

1 1 0 0             2 2 0 0
1 0 1 0             2 0 3 0
1 0 1 0      =>  2 0 3 0
0 1 1 0             0 3 3 0 
1 0 0 1             4 0 0 5

 

2. 이제 다시 배열을 순회하며 0인 칸들에서 사방을 탐색해서 인접한 그룹들(중복 안되도록 조심)의 사이즈의 합 +1을 구한다. 이게 현재 0인 칸을 1로 바꿨을 때 만들 수 있는 모양의 크기이다. 이 중 가장 큰 값을 구하면 된다.