백준 2638번
https://www.acmicpc.net/problem/2638

문제

후기

⏰ 풀이시간 1시간 ++⏰

얼마전에 작성 하였던 #2636 치즈와 거의 똑같은 문제다.

단지 차이점은, 치즈가 한 면의 바깥 공기에만 닿아도 녹느냐, 바깥 공기에 두 면 이상 닿아야

녹느냐의 문제이다.

remove_cheese에서 치즈가

(위오른쪽), (위아래), (위왼쪽), (오른쪽아래), (오른쪽왼쪽), (아래왼쪽)

총 6가지 경우에 대하여 녹을 수 있도록 코드를 추가했다.

이 외에는 2636 치즈와 같은 문제이므로 쉽게 해결할 수 있었다.

나의 풀이

import sys

input = sys.stdin.readline

sys.setrecursionlimit(10**7)

n, m = map(int,input().split())

graph= [] 

for i in range(n):

    graph.append(list(map(int,input().split())))

visited= [ [False] * m for _ in range(n)]

# 풀이순서 cheese의 양을 체크해서 0이 아니면 반복실행  

# 바깥에 있는 공기들을 우선 9로 전부 바꾸고 ( 바깥공기 안쪽공기 판별 )

# 9에 접해있는 치즈들은 모두 녹인다.

# 한번에 모두 제거한다. time을 1 증가시킨다. 현재 남은 치즈의 양을 저장한다. 

# visited를 초기화하고, 반복한다. 


def check_cheese(x,y):  # 공기가 바깥공기 인지 판별하는 함수

    if x<=-1 or x>=n or y<=-1 or y>=m :

        return False
    
    if not visited[x][y] and (graph[x][y] ==0 or graph[x][y]==9):

        graph[x][y] = 10   #무한루프를 돌지않기 위해 일단 10으로 만들어 놓고

        check_cheese(x,y-1)
        check_cheese(x,y+1)
        check_cheese(x+1,y)
        check_cheese(x-1,y)

        return True

    return False



def remove_cheese(x,y):  #치즈가 바깥 공기에 닿아있는지 판별하는 함수
    global cncnt
    global cnt

    if x<=-1 or x>=n or y<=-1 or y>=m:

        return False
    

    if not visited[x][y] and graph[x][y] == 1 and ( ( graph[x][y+1] ==9 and graph[x+1][y] == 9 ) or ( graph[x][y+1] ==9 and graph[x][y-1] == 9 ) or 
    ( graph[x][y+1] ==9 and graph[x-1][y] == 9 ) or ( graph[x+1][y] ==9 and graph[x][y-1] == 9 ) or ( graph[x+1][y] ==9 and graph[x-1][y] == 9 ) or ( graph[x][y-1] ==9 and graph[x-1][y] == 9 )):

        graph[x][y] = -3

        cnt +=1  #녹을 치즈의 양이다.

        return True
    
    return False



cheese = 0  #전체치즈의양
now_cheese = [] #현재 치즈의 양을 저장할 리스트
time = 0  #치즈를 녹이는데 걸릴시간



#치즈의 양을 그래프를 돌며 구한다. 전체 치즈의 양을 구해야 치즈가 0이 됐을 때 함수를 종료할 수 있기 때문
for i in range(n):

    for j in range(m):

        if graph[i][j] == 1:

            cheese+=1



while True:  #치즈가 0이 되기 전까지 계속 돌예정

        
    if cheese ==0: 
        print(time)
        exit()


    check_cheese(0,0)

    #graph를 돌면서 10으로 만들어 두었던 공기들을 바깥 공기인 9로 만든다. 무한loop를 돌지않기위한 작업

    for i in range(n):

        for j in range(m):

            if graph[i][j]==10:

                graph[i][j] = 9  
    
    
    visited= [ [False] * m for _ in range(n)]  #바깥 공기를 돌며 visited를 사용했기때문에 초기화를 해준다.

    cnt = 0 #치즈가 몇개 녹을 예정인지도 초기화


    for i in range(n):

        for j in range(m):

            if not visited[i][j]:

                remove_cheese(i,j)  #치즈를 제거할 준비

    cheese -= cnt


    for i in range(n):

        for j in range(m):

            if graph[i][j]==-3:

                graph[i][j] = 9  #치즈가 녹았다



    time +=1 # 모든 작업이 끝났으니 1시간 경과한다.