백준 2638 : 치즈

https://www.acmicpc.net/problem/2638

2638번: 치즈

https://github.com/HPYoo/swcodingtest/commit/716810365e38791aecdf888ce59fe6326474cf17

sw coding 2638 update(Baekjoon) · HPYoo/swcodingtest@7168103

1. 생각 흐름 정리하기

 -1) 치즈의 빈공간 탐색하기 (내/외부 판단)

 -2) 녹을 치즈 결정 

 -3) 녹는다~ 녹아 치즈가~

 -4) Count += 1

 -5) 치즈가 다 녹을때까지 반복

 

2. 전체 코드

 메모리 : 163564 KB 시간 : 392 ms 풀이시간 : 30:37

메모리 제한은 128 MB 이나 파이썬 메모리 보너스로 가장 로드가 컸던 항목이 메모리 제한 X3 + 128 MB 를 넘지 않으면 된다고 명시되어있다. 하지만, 각 코딩테스트를 주관하는 기업들에서는 어떻게 다룰지 모르니 최대한 메모리를 넘지 않도록 하자... 다음에 다시 풀어보면서 메모리 관리 해보자! 보자마자 바로바로 풀 수 있어서 신났다가 실망함

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]

# 상 하 좌 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# Find Outer
def outer():
    # 가장자리 조사
    visited = [[False for _ in range(M)] for _ in range(N)]
    for i in range(N):
        if 0 < i < N - 1 :
            j_arr = [0, -1]
        else :
            j_arr = [k for k in range(M)]
        for j in j_arr :
            q = [[i, j]]
            visited[i][j] = True
            while q :
                x, y = q[0]
                del q[0]
                for d in range(4):
                    nx = x + dx[d]
                    ny = y + dy[d]
                    if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny] :
                        if board[nx][ny] == 0 :
                            visited[nx][ny] = True
                            q.append([nx, ny])
    return visited

# Find outline of cheese
def cheese(x, y, v):
    cnt = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if v[nx][ny] :
            cnt += 1
    if cnt >= 2 :
        return True
    else :
        return False

# Solve
def solve():
    it = 0
    init_cheese = 0
    info_c = []
    for i in range(N):
        init_cheese += board[i].count(1)
        for j in range(M):
            if board[i][j] == 1 :
                info_c.append([i, j])
    while True :
        temp = []
        visit = outer()
        if init_cheese == 0 :
            break
        for x, y in info_c :
            check = cheese(x, y, visit)
            if check :
                board[x][y] = 0
                init_cheese -= 1
            else :
                temp.append([x, y])
        info_c = temp
        it += 1
    return it

print(solve())