[알고리즘] 백준16932 모양만들기 - 파이썬

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

16932번: 모양 만들기

 

 

[틀린 풀이 코드]

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

N, M = map(int, input().split())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))


zero_list = []
for i in range(N):
    for j in range(M):
        if graph[i][j] == 0:
            zero_list.append((i, j))

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
def bfs(i, j):
    cnt = 1
    visited = [[False] * M for _ in range(N)]
    q = deque()
    q.append((i, j))
    visited[i][j] = True
    while q:
        y, x = q.popleft()
        for l in range(4):
            yy = dy[l] + y
            xx = dx[l] + x
            if 0 <= xx < M and 0 <= yy < N:
                if graph[yy][xx] == 1 and not visited[yy][xx]:
                    visited[yy][xx] = True
                    q.append((yy, xx))
                    cnt += 1
    return cnt


result = 0
for a, b in zero_list:
    # print("test", a, b)
    graph[a][b] = 1
    result = max(result, bfs(a, b))
    graph[a][b] = 0

print(result)

• 문제를 읽자마자 이게 왜 골드 문제인가 의아했던 문제.. 였으나 역시 시간 초과 위 코드는 배열에 0을 만날 때마다 1로 바꿔주고 연결된 1의 개수를 bfs로 세도록 구현했다.
  
  
• 시간 초과를 어떻게 해결해야 할지 더 좋은 방법이 필요했고 다른 블로그들의 글을 보고 이해했는데 배열의 '1'을 그룹핑해주는 것이 이 문제의 해결법이었다.

 

[정답 풀이 코드]

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

N, M = map(int, input().split())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))
visited = [[0] * M for _ in range(N)]

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
def bfs(i, j):
    cnt = 1
    q = deque()
    q.append((i, j))
    visited[i][j] = num
    while q:
        y, x = q.popleft()
        for l in range(4):
            yy = dy[l] + y
            xx = dx[l] + x
            if 0 <= yy < N and 0 <= xx < M:
                if not visited[yy][xx] and graph[yy][xx] == 1:
                    visited[yy][xx] = num
                    q.append((yy, xx))
                    cnt += 1
    return cnt

# '1' 그룹화 진행 -> num은 2부터 시작
num = 2
group = dict()
for i in range(N):
    for j in range(M):
        if graph[i][j] == 1 and not visited[i][j]:
            cnt = bfs(i, j)
            group[num] = cnt
            num += 1
# print(group)
# print(visited)

result = 0
for y in range(N):
    for x in range(M):
        if graph[y][x] == 0:
            s = set()
            for l in range(4):
                yy = dy[l] + y
                xx = dx[l] + x
                if 0 <= yy < N and 0 <= xx < M:
                    if graph[yy][xx] == 1 and visited[yy][xx] not in s:
                        s.add(visited[yy][xx])
            res = 1
            # print("test", s)
            for ss in s:
                res += group[ss]
            result = max(result, res)
print(result)

• 먼저, 1을 bfs로 탐색하면서 그룹핑해준다. 그룹핑은 num변수를 1씩 올려주면서 진행했다. 예제 입력 1을 예시로 든다면 visited배열이 {2 : 3,  3 : 1}로 나오는데 이는 그룹 2는 1이 3개, 그룹 3은 1이 1개라는 뜻이다. 그룹 넘버(num)를 2부터 시작한 이유는 왜.. 그랬지? 1로 해도 될 것 같다.
  
  
• 그리고 배열에서 0을 순차적으로 돌면서 배열에 인접한 1을 만날때 그 1이 어떤 그룹인지 확인하고 set에 넣어준다. 만약, 중복된다면 넣어주지 않는다.
  
  
• 마지막으로 set에 들어있는 그룹넘버를 가지고 합을 구하고 최댓값을 result에 저장하여 출력했다.