[백준]2638 - 치즈 (#파이썬 #두 가지 접근 방식의 차이)

‘flag를 어디에 세울 것인지’에 따라 시간 복잡도가 N의 제곱만큼 차이가 났다. 현재 문제에서 N은 최대 100이므로 TLE가 발생하는지 안 하는지 차이를 내는 중요한 요인이었다.

2638번: 치즈

문제 요약

숫자 1로 표현된 치즈가 몇 번의 연산 후에 모두 녹을지 구하는 문제이다. 치즈(숫자 1)는 주변에 숫자 0이 2개 이상 있는 경우 해당 연산에서 녹게 된다. 다만, 숫자 0 중 치즈에 둘러싸인 것은 제외한다는 조건이 있어 다소 까다롭다.

1트: counting되면 안 되는 영역을 표시한다

숫자 1이 모든 숫자 0과 맞닿는 경우를 센다면 쉬운 문제였겠지만, 숫자 1로 만들어진 영역 내에 포함된 숫자 0은 counting 하지 않아야 하여 까다로운 문제가 되었다.

숫자 1로 만들어진 영역 내의 숫자 0을 숫자 2로 할당하여 counting 되면 안 되는 영역으로 표시하였다. 이 영역을 표시할 때는 BFS를 사용하였다.

for i in range(1, N-1):
    for j in range(1, M-1):
        if original_matrix[i][j] == 1: isStop = False
        if original_matrix[i][j] == 0 and vis[i][j] == 0:
            isInside = [True]
            vis[i][j] = 1
            bfs(i, j)
deleteOuter() // 주변의 숫자 0 개수를 세서 숫자 1 중 지울 수 있는 것을 지운다

• 순회하며 BFS를 적용하는 코드

def bfs(i, j):
    qu.append([i, j])
    while qu:
        i, j = qu.popleft()
    
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]
        
        for k in range(4):
            nx = i + dx[k]
            ny = j + dy[k]
            if 0 <= nx and nx < N and 0 <= ny and ny < M:
                if original_matrix[nx][ny] == 0:
                    qu.append([nx, ny])
                    original_matrix[nx][ny] = 2

BFS만 연산하면 괜찮았겠지만, BFS를 품고 있는 두 개의 반복문이 문제가 되었다. 해당 순회가 필요한 이유는 BFS를 시작해야 하는 영역을 순회 없이 특정하기 어려웠기 때문이다. 즉, 모든 지점에서 BFS를 통해 숫자 1 영역에 포함된 숫자 0인지 판단한 것이다.

이 경우 시간 복잡도는 O(NMO(BFS)) = O(NMN*M)으로 N, M ≤ 100일 때 TLE가 발생한다!

2트: counting되어야 하는 영역을 표시한다

항상 숫자 0인 지점 (0, 0)부터 BFS로 counting 되어야 하는 영역을 표시한다. 이 영역을 표시할 때는 BFS를 사용하였다.

vis = [[0 for _ in range(M)] for _ in range(N)]
vis[0][0] = 1
bfs(0, 0)
deleteOuter()

 

항상 숫자 0인 (0, 0)지점에서 BFS를 수행할 경우 숫자 1로 만들어진 영역 내에 포함된 숫자 0에는 표시되지 않게 된다(위 BFS 함수 참고).

이렇게 BFS를 통해 counting되어야 하는 영역에 2를 표시해 두고, deleteOuter() 함수에서 숫자 2의 개수를 counting 하여 삭제할 숫자 1을 결정한다.

이 경우 시간 복잡도는 O(O(BFS)) = O(N*M)으로 N, M ≤ 100일 때 충분히 연산 가능한 수준이다.

 

(참고) 숫자 1을 삭제하는 순간 결정

‘1트’ 경우에 숫자 0이 주변에 몇 개가 있는지 counting하게 된다. Counting 후 곧바로 숫자 1을 0으로 바꾸면 다른 숫자 1의 주변에 숫자 0이 몇 개가 있는지 counting 할 때, 직전에 바꿨던 값이 반영된다.

이런 경우 보통 방문 이력 표시 변수에 특정 값을 할당하여 모든 숫자 1에 대해 counting을 끝낸 후에서야 숫자 1을 0으로 바꾸는 작업을 수행한다.

‘2트’의 경우 ‘2’의 개수를 counting하여 조건을 만족하는지 확인하는 것으로 바뀌었기 때문에 곧바로 숫자 1을 0으로 바꾸어도 무방하였다.

 

💡 매우 유사한 접근인데 시간 복잡도에서 이렇게 큰 차이가 날 수 있다는 것이 놀라웠다.

📁코드 전문