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

문제

후기

⏰ 풀이시간 4시간 ++⏰

상당히 힘들었다. 우선 바깥 공기와 치즈 안쪽 공기판별을 위한 생각을 떠올리는 데 시간을 한참 소모했다.

내린 결론은 그래프의 (0,0) 지점부터 시작해 닿을 수 있는 모든 부분은 바깥 공기라는 것이다.

다음 해결책은 녹일 치즈를 고르는 것이다.

이는 DFS를 돌며 치즈의 상하좌우에 바깥 공기가 하나라도 닿아 있으면 1시간 뒤에 녹는다는 알고리즘을 구현했다.

이 과정에서 DFS 안에서 무한루프가 일어나, 해결을 위한 생각을 한참 했는데, 결론은 While 안에서 한 번 더 그래프 전체를 돌며 초기화하는 것이다. 불필요한 메모리, 시간이 소요되지만, 아직은 나의 실력이 이 문제를 해결하기엔 부족한 것 같다.

처음엔 코드가 원하는 대로 실행되지 않아 무엇이 계속 문제일까 라는 생각을 정말 많이 했다.

문제점은 check_cheese와 remove_cheese에서 무한루프가 계속 발생하는 것이었다.

그래프와 DFS , BFS에 대한 개념이 완벽하지 않다면, 함수 중간에 print(graph) 등을 입력하여 어느 부분에서
에러가 발생하는지 보면서 코드를 고쳐간 덕분에 해결할 수 있었던 것 같다.

추후 시간과 메모리를 더 줄이는 방법으로 풀어볼 예정

나의 풀이

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 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 or graph[x][y+1] ==9 or graph[x-1][y] == 9 or 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)
        print(now_cheese[-1])
        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 #치즈가 몇개 녹을 예정인지도 초기화
    
    now_cheese.append(cheese) #현재 치즈의 값을 리스트에 저장해 두어야 문제에서 요구한 "한 시간 전에 남아있는 치즈의 개수" 를 출력가능
    

    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시간 경과한다.