[BOJ] 16932번 - 모양 만들기
이전 글의 포스팅에서 시간초과를 다루었고 이번에도 시간초과에 관해 포스팅 할 것이다.
글쓴이는 문제들을 풀면서 새로운 방법이라던지, 내가 새로 알게된 것들에 대해서 주로 글쓰는 편이다.
개발에 관한것들도 써내려가야 할 것들이 많은데.. 현재는 알고리즘 문제 푸는 것이 좀 더 재밌는것 같다.
저번과 같이 직관적으로 모든 경우의 수를 빠른 시간 내 짜봤다. 테스트 케이스는 돌아가나 문제가 노린것이 그건 아니였나보다.
첫번째 시도 : 모든 경우에서의 bfs를 돌려봤기 때문에 실패했다.
두번째 시도 : bfs를 만들 때 항상 check배열을 만들었으므로, check배열의 횟수를 줄이기 위하여 해당하는 조건만 bfs를 돌리게 했다.
역시나 둘다 시간초과이다.. 답을 노린것이 아니라 어떻게 효율적으로 할 것이냐가 중요한것 같다.
그렇다면 시간초과를 해결하려면 어떤 식으로 해야할까?
16932번: 모양 만들기
N×M인 배열에서 모양을 찾으려고 한다. 배열의 각 칸에는 0과 1 중의 하나가 들어있다. 두 칸이 서로 변을 공유할때, 두 칸을 인접하다고 한다. 1이 들어 있는 인접한 칸끼리 연결했을 때, 각각의
www.acmicpc.net
위 시도를 해봤을 때, 조건에 맞는 원소를 기준으로 bfs를 돌리면서 check[][]배열을 만드는 것은 시간이 매우 오래 걸리는것 같았다.
그래서 한 몇십분 동안 고민하며 생각한 알고리즘은 이것이다.
1. 번호를 매기면서 해당 구역들의 크기를 저장해보자. (아래 그림 참고)
2. 해당 구역 번호와 크기를 이용해 만약 0인 값이 1이 되었을 경우, 어떻게 될 것인가 생각해본다.
0 -> 1로 바뀐 원소 주변에 1구역과 3구역이 있다면 [해당 지역의 크기] = (1구역의 크기 + 3구역의 크기 + 1) 가 된다.
< 주의: 같은 지역이 2번이상 있는 경우도 있음을 고려한다. >
1번에 해당하는 참고자료
구역을 나눈 그림을 보았을 때 문제에서 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)