치즈 ( 2638 번 )

2638번: 치즈

 

나의 풀이

from collections import deque
import sys

def _make_list(n):
    answer = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
    return answer


def _expansion_out(start_x, start_y):
    queue = deque([(start_x, start_y)])
    map_list[start_x][start_y] = 'e'
    while queue:
        x, y = queue.popleft()
        for n_x, n_y in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
            if (0 <= n_x < n) and (0 <= n_y < m) and (map_list[n_x][n_y] == 0):
                map_list[n_x][n_y] = 'e'
                queue.append((n_x, n_y))
        

def _main(n, m, map_list):
    answer = 0
    _expansion_out(0, 0) # 초기 외부 확장

    while True:
        check, no_cheeze = True, []
        for i in range(n):
            for j in range(m):
                if map_list[i][j] == 1: # 치즈!!
                    check, e_count = False, 0
                    for n_i, n_j in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
                        if map_list[n_i][n_j] == 'e':
                            e_count += 1
                    if (e_count >= 2):
                        no_cheeze.append((i, j))
        for del_x, del_y in no_cheeze: # 치즈 녹여주기
            _expansion_out(del_x, del_y)

        if check: # 녹은 치즈가 없으면 멈춰!!
            break
        answer += 1
    return answer

n, m = map(int, sys.stdin.readline().rstrip().split())
map_list = _make_list(n)
print(_main(n, m, map_list))

 

시간 복잡도

while True : 치즈가 녹을떄까지 반복 ( 이차형 시간 복잡도 )
    # map을 탐색 ( 이차형 시간 복잡도 )
	for i in range(n):
		for j in range(m):
        
해당 알고리즘 시간 복잡도 : 사차형 시간 복잡도 ( O( n**4 ) )