백준 16946 - 벽 부수고 이동하기 4

문제 설명

 

입출력 및 제한 사항

풀이

문제를 요약해보자면, 벽이 있는 위치에서 시작해서 시작 위치의 벽이 부숴졌을 때 이동할 수 있는 공간의 넓이를 계산하는 문제이다. 사실 별 생각 없이 n, m이 1000이라서 모든 위치를 start 배열에 넣고 bfs를 돌렸다가 시원하게 시간초과 받았다...

 

ㅎㅎ 시간 복잡도 계산 꼼꼼히 하기~!

해당 풀이에서 시간 초과가 나는 경우는 다음과 같다

111111...11111

10000...0001

10000...0001

.....

111111...111111

만약 이렇게 생긴 1000*1000 matrix가 있다고 치면 모든 벽(4000)에서 998*998인 영역에 대해 bfs탐색을 하게 되고 4000 * 1000*1000 이라는 O(n^3)의 시간 복잡도가 나오게 된다. 따라서 중복된 공간을 탐색할 땐 또 계산하지 않고 처음만 공간을 계산하고 마스킹해놓는다면 다른 벽에서 해당 공간에 대해 탐색 땐 전부를 탐색하는 것이 아니라 미리 마스킹한 값만 보면 된다.

 

그렇게 풀이하기 위해서는 두 가지 추가적인 표시가 필요하다.

1. 연속된 공간이라는 표시

2. 공간 크기에 대한 표시

 

공간이 연속된 공간이라는 표시는 다음과 같은 예시를 들어서 확인할 수 있다.

1011

0011

-> (0, 0)에서 계산할 때 오른쪽과 아래가 연속된 공간으로 덮혀있다. 같은 공간에 대해 중복 계산을 방지하기 위해 연속된 공간은 알아볼 수 있는 표시를 해주어야 한다. 이제 코드를 확인해보자.

내 코드

from collections import deque
import sys
input = sys.stdin.readline
mis = lambda: map(int, input().split())

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

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

# area[i][j] = 0구역의 개수(없으면 -1)
area = [[-1] * m for _ in range(n)]
sizes = [0]  # sizes[idx] = idx 라벨의 0-구역 크기

def bfs(start, idx):
    queue = deque([start])
    area[start[0]][start[1]] = idx
    
    ret = 1
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < n and 0 <= ny < m and area[nx][ny] == -1 and not matrix[nx][ny]:
                queue.append((nx, ny))
                area[nx][ny] = idx
                ret += 1
    
    return ret

idx = 0
for i in range(n):
    for j in range(m):
        if matrix[i][j] == 0 and area[i][j] == -1:
            idx += 1
            sizes.append(bfs((i, j), idx))

ans = []
for i in range(n):
    row = []
    for j in range(m):
        if matrix[i][j] == 0:
            row.append('0')
        else:
            visited = set()
            s = 1
            for k in range(4):
                ni = i + dx[k]
                nj = j + dy[k]
                
                if 0 <= ni < n and 0 <= nj < m:
                    gid = area[ni][nj]
                    
                    if gid != -1 and gid not in visited:
                        s += sizes[gid]
                        visited.add(gid)
                        
            row.append(str(s % 10))
            
    ans.append(''.join(row))

print('\n'.join(ans))

area 배열에 각 공간이 연속된 공간인지 인덱스로 마스킹을 해놓은 뒤 size 배열에 해당 인덱스에 대한 공간의 크기를 적어두었다.
이후 matrix를 확인하면서 벽이라면 상하좌우만 판단하여 올바른 값을 계산 후 정답 배열을 구성한다.

 

시간 복잡도

0공간 탐색 및 크기 측정: O(nm)

각 벽에 대해 상하좌우만 탐색: O(nm)

고찰

별다른 고민 사항은 없었던 것 같다. 직관적으로 생각해서 시간 복잡도를 대충 계산하지 않도록 조심해야겠다!