백준 #2636

<문제 링크>

 

반복문 (= 이번에 어느 치즈 칸이 녹을지 BFS로 탐색)

* 공기와 접촉하고 있는 치즈만 녹으므로, 공기인 칸에서부터 시작해서 BFS로 탐색하여 치즈인 부분을 찾기
* BFS이므로 queue를 사용하여 4가지 방향(상,하,좌,우)에 대하여 탐색한다.
* visit배열을 사용해서 BFS로 탐색 시 방문했던 영역의 중복방문을 피한다.
* 공기인 부분에서 한 칸 이동 시 치즈이면 녹을 영역이므로 -1로 표시한다.

 

출력해야할 것
1) 치즈가 모두 녹는 데 걸리는 시간
2) 모두 녹기 한 시간 전에 남아 있는 치즈 조각의 칸 수

치즈가 모두 녹는 데 걸리는 시간 = 반복문의 호출 수

녹기 한 시간 전에 남아있는 치즈 조각의 수 = ( 반복문을 호출할 때마다 녹는 치즈 수를 파악)
                                                                                  가장 마지막에 호출된 반복문 실행 시 녹은 조각을 count

반복문 호출할 때마다 녹는 치즈 수를 파악하기 위해서 visit 배열 체크 시 방문여부를 1 or 0으로 체크하는 것이 아니라, 반복문이 '몇 번째로 호출되었는지'로 체크

예를 들면, 

첫 번째 반복문 호출 시 제거되는 치즈에 대하여 visit 배열을 다음과 같이 체크한다.

첫 번째 반복문 호출 시 제거되는 치즈에 대하여 visit 배열을 다음과 같이 체크한다.

#cheese 문제
n_calls = 0
n_cheese = 0
n_melt = 0

#치즈 array 받기
m, n = map(int, input().split())
arr = list()
for i in range(m):
    temp = list(map(int, input().split()))
    n_cheese += temp.count(1)
    arr.append(temp)

#방문 배열 초기화
visit = dict()
for i in range(m):
    for j in range(n):
        visit[i, j] = 0

directions = [[-1, 0], [0, 1], [1, 0], [0, -1]]

#BFS 탐색
def bfs():
    global arr
    
    #start point 지정
    i, j = 0, 0
    while arr[i][j] != 0:
        i += 1
        
    if arr[i][j] == 0:
        q = list()
        q.append([i, j])
    
    while q:
        now = q.pop(0)
        for d in directions:
            dr = now[0] + d[0]
            dc = now[1] + d[1]
            #새로운 좌표값이 탐색가능 영역 안에 있는지 체크
            if (dr < 0 or dr >= m or dc < 0 or dc >= n):
                continue
            #새로운 좌표에 방문한 적 있는지 체크
            if visit[dr, dc] >= n_calls:
                continue
            #공기랑 닿는 치즈인지 확인해서 -1로 바꿔주기
            if arr[dr][dc] == 1:
                visit[dr, dc] = n_calls
                arr[dr][dc] = -1
                continue
            #아무 조건에도 해당하지 않으면 탐색 계속    
            visit[dr, dc] = n_calls
            q.append([dr, dc])

            
#녹는 치즈 면적 계산
def count():
    cnt = 0
    global arr
    for i in range(m):
        for j in range(n):
            if arr[i][j] == -1:
                cnt += 1
                arr[i][j] = 0
    return cnt
                
while  n_cheese > 0:
    n_calls += 1
    bfs()
    n_melt = count()
    n_cheese -= n_melt
    
print(n_calls)
print(n_melt)