백준 2638 치즈 (dfs + bfs)

https://www.acmicpc.net/problem/2638
상, 하, 좌, 우로 인접하고 값이 1인 치즈의 테두리값을 지워나가서 모든 치즈가 녹을 때까지 걸리는 시간을 구하는 문제다.

조건이 하나있는데 치즈 내부에 빈공간에 대해서는 노출된 면이 2면이어도 녹지 않는다는 것이다.

따라서 내부의 빈공간을 다른 값으로 마킹해야하는 것이 중요하다고 생각했다.

내부의 공간을 하는 것보다 외부의 값을 마킹하고 나머지 0부분을 내부값으로 쓰는 것이 좋다고 생각해서

외부값을 먼저 -1로 치환하고 난 다음, 치즈 테두리의 상하좌우값이 -1인것이 2개 이상이면 녹이고 나서

내부의 0을 다시 -1로 치환하는 방식으로 풀었다.

순서는 다음과 같다.

1. 바깥에 이어져있는 0을 모두 -1로 치환한다.
2. 각 치즈의 좌표에서 인접한 상하좌우값이 -1인게 2개 이상이면 녹여질 대상이므로 해당 좌표를 list에 넣는다.
3. 녹여질 대상의 좌표를 꺼내면서 해당 좌표의 상하좌우를 계속 탐색해나가면서 -1로 치환해낸다.
4. 테두리도 -1로 변환한다.
5. 녹일 치즈가 있으면 답을 += 1 한다.

N, M = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(N)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
import sys

sys.setrecursionlimit(10 ** 6)

def marking_outside_cheese(x, y):
    if lst[x][y] == -1:
        return
    lst[x][y] = -1
    for i in range(4):
        mx, my = dx[i] + x, dy[i] + y
        if 0 <= mx < N and 0 <= my < M:
            if lst[mx][my] == 0:
                marking_outside_cheese(mx, my)


def is_border(x, y):
    cnt = 0
    for i in range(4):
        mx, my = dx[i] + x, dy[i] + y
        if 0 <= mx < N and 0 <= my < M:
            if lst[mx][my] == -1:
                cnt += 1
    if cnt >= 2:
        return True
    return False


def solution(N, M, lst):
    answer = 0
    loop_cnt = max(N, M)  # 둘 중 큰값이 치즈를 녹이는데 필요한 최대 시간
    marking_outside_cheese(0, 0)  # 치즈 바깥값 -1로 치환
    for _ in range(loop_cnt):
        cheess_loc = []
        for i in range(N):
            for j in range(M):
                if lst[i][j] == 1 and is_border(i, j):  # 치즈가 테두리인지 확인
                    # lst[i][j] = -1 # 테두리면 시간초 추가하고 녹여버림 - 모든 치즈에 대해 녹여야함 한번에
                    cheess_loc.append([i, j])  # 테두리 좌표 추가
                # if lst[i][j] == 0: #녹인 후 0에 해당하는 부분을 찾아서 -1로 치환
                #     marking_outside_cheese(i, j)
        # cheess_loc => 녹을 수 있는 모든 테두리 좌표
        if cheess_loc:  # 녹을 수 있는게 있으면 답 ++
            answer += 1
        for loc in cheess_loc:
            x, y = loc
            marking_outside_cheese(x, y)
            lst[x][y] = -1
            # answer += 1
    return answer


print(solution(N, M, lst))

# 8 9
# 0 0 0 0 0 0 0 0 0
# 0 0 0 0 0 0 0 0 0
# 0 1 1 0 0 0 1 1 0
# 0 1 0 1 1 1 0 1 0
# 0 1 0 0 1 0 0 1 0
# 0 1 0 1 1 1 0 1 0
# 0 1 1 0 0 0 1 1 0
# 0 0 0 0 0 0 0 0 0

 

> 재귀 런타임에러가 걸려서 재귀호출 limit를 지정한 풀이라 다시 풀어보아야함.