[BOJ] 16932번 - 모양 만들기

이전 글의 포스팅에서 시간초과를 다루었고 이번에도 시간초과에 관해 포스팅 할 것이다.

글쓴이는 문제들을 풀면서 새로운 방법이라던지, 내가 새로 알게된 것들에 대해서 주로 글쓰는 편이다.

개발에 관한것들도 써내려가야 할 것들이 많은데.. 현재는 알고리즘 문제 푸는 것이 좀 더 재밌는것 같다.

 

저번과 같이 직관적으로 모든 경우의 수를 빠른 시간 내 짜봤다. 테스트 케이스는 돌아가나 문제가 노린것이 그건 아니였나보다.

첫번째 시도 : 모든 경우에서의 bfs를 돌려봤기 때문에 실패했다.

두번째 시도 : bfs를 만들 때 항상 check배열을 만들었으므로, check배열의 횟수를 줄이기 위하여 해당하는 조건만 bfs를 돌리게 했다.

 

역시나 둘다 시간초과이다.. 답을 노린것이 아니라 어떻게 효율적으로 할 것이냐가 중요한것 같다.

그렇다면 시간초과를 해결하려면 어떤 식으로 해야할까?

 

www.acmicpc.net/problem/16932

16932번: 모양 만들기

위 시도를 해봤을 때, 조건에 맞는 원소를 기준으로 bfs를 돌리면서 check[][]배열을 만드는 것은 시간이 매우 오래 걸리는것 같았다.

그래서 한 몇십분 동안 고민하며 생각한 알고리즘은 이것이다.

 

1. 번호를 매기면서 해당 구역들의 크기를 저장해보자. (아래 그림 참고)

 

2. 해당 구역 번호와 크기를 이용해 만약 0인 값이 1이 되었을 경우, 어떻게 될 것인가 생각해본다.

0 -> 1로 바뀐 원소 주변에 1구역과 3구역이 있다면 [해당 지역의 크기] = (1구역의 크기 + 3구역의 크기 + 1) 가 된다.

< 주의: 같은 지역이 2번이상 있는 경우도 있음을 고려한다. >

 

1번에 해당하는 참고자료

bfs()통한 구역 나누기

구역을 나눈 그림을 보았을 때 문제에서 0을 1로 바꿀 때 영역의 길이의 최댓값을 구하라 했다.

예를들어 다음 그림을 보자

다음 그림에서 보라색부분의 0을 1로 바꾸었을 때, 주변에 있는 덩어리들(2와 3) 의 넓이 값은 몇인지 바로 알 수 있다. (1번에서 구함)

 

주의할 점은 아래, 위, 왼쪽, 옆 중 같은 값들이 섞여있을 수도 있기 때문에 중복제거만 해주면 된다. 

 

 

from sys import stdin
from itertools import combinations
from collections import deque

std = stdin.readline

R, C = map(int, std().split())

arr = []
for i in range(R):
    arr.append(list(map(int, std().split())))
q = deque()
check = [[0 for i in range(C)] for j in range(R)]
nr, nc = [0, 1, 0, -1], [1, 0, -1, 0]
region = {0: 0}
region_num = 0
answer = 0


def bfs():
    global answer
    cnt = 1
    while q:
        r, c = q.popleft()
        for i in range(4):
            dr, dc = r+nr[i], c+nc[i]
            if 0 <= dr < R and 0 <= dc < C and check[dr][dc] == 0 and arr[dr][dc] == 1:
                check[dr][dc] = region_num
                cnt += 1
                q.append((dr, dc))
    region[region_num] = cnt
    return


for i in range(R):
    for j in range(C):
        if arr[i][j] == 1 and check[i][j] == 0:
            region_num += 1
            check[i][j] = region_num
            q.append((i, j))
            bfs()

for i in range(R):
    for j in range(C):
        if arr[i][j] == 0:
            around = []
            for k in range(4):
                dr, dc = i+nr[k], j+nc[k]
                if 0 <= dr < R and 0 <= dc < C:
                    around.append(check[dr][dc])
            around = set(around)
            ans = 1
            for s in around:
                ans += region[s]

            if ans > answer:
                answer = ans

print(answer)