[백준] 2638번 치즈 - 파이썬/DFS

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

import sys
sys.setrecursionlimit(10**6)

N,M = map(int,input().split())

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

t = 0

# graph에서 외부 공기는 2로 변환시키는 함수
def background(a,b,visited):

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

    graph[a][b]=2

    visited[a][b]=True

    for i in range(4):
        nx = a + dx[i]
        ny = b + dy[i]

        if 0<=nx<N and 0<=ny<M:
            if not visited[nx][ny] and (graph[nx][ny]==0 or graph[nx][ny]==2):
                visited[nx][ny]=True
                graph[nx][ny]=2
                background(nx,ny,visited)

# 외부와 맞닿은 갯수 체크
def arround(a,b):

    cnt = 0

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

    for i in range(4):
        nx = a + dx[i]
        ny = b + dy[i]

        if graph[nx][ny]==2:
            cnt+=1

    return cnt

while True:

    t += 1
    ch_list = []
    visited = [ [ False for _ in range(M)] for _ in range(N) ]
    background(0,0,visited)

    for i in range(N):
        for j in range(M):
            if graph[i][j]==1 and arround(i,j) >1:
                ch_list.append((i,j))

    for i in ch_list:
        graph[i[0]][i[1]] = 2

    check = True

    for i in range(N):
        for j in range(M):
            if graph[i][j]==1:
                check = False

    if check:
        break

print(t)

비슷한 문제를 코딩테스트에서 풀었던 기억이 있어 같은 로직을 적용했다.

같은 공기지만 치즈 외부와 내부의 공기라는 차이점이 있기 때문에 치즈 외부의 공기는 graph 에서 2로 변환시켜주는 DFS 함수를 만들었다.

모눈종이에서 외곽은 항상 공기라는 조건이 있기 때문에 (0,0)에서만 DFS를 돌려준다.

순서는 다음과 같다.

1. (0,0)에서 DFS 함수로 외부 공기를 2로 바꿔준다.
2. graph 값이 1이고 주변에 맞닿은 칸이 2칸 이상인 좌표를 특정 리스트에 담는다.
3. 모든 좌표 반복이 끝나면 특정 리스트에 있는 좌표는 값을 2로 변경시킨다.
4. 종료조건을 체크해준다.