2638 치즈 (미완)

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

* 아이디어

후..

치즈 녹는걸 어떻게 구현하지?

하루(day++) 지나면, 사방(상/하/좌/우)조사해서,

2방향 이상 공기(0)와 맞닿아있는 칸은 공기(0)화 됨.

또 하루(day) 지나면, 치즈(1)인 칸 dfs로 전부 돌면서 각각 사방 조사해서,

2방향 이상 공기(0)와 맞닿아있는 칸의 값을 0으로 만듦.

단, 전체 조사 끝나고 난 후, 한꺼번에 0으로 값을 바꿔야 함. 그래야 같은 날에 녹는걸 표현할 수 있음.

===>음..그걸 어떻게 구현하지?

2방향 이상 공기와 맞닿은 칸의 좌표를 큐에 저장할까!?

조사 다 끝난 후, 큐를 하나씩 pop하면서 해당 좌표에 0을 넣는거지!!!

===> 함수로 따로 빼야겠군, 녹는걸 표현하는 함수 : melting()

==> 하루가 지나는건 전역변수로 int day; 선언하구.

===> 치즈(1)인 칸을 조사하는 함수도 따로 빼자. : dfs(0, 0)

좌표상의 모든 칸을 for문으로 돌면서, 값이 1인 칸을 만났을 때, 그 좌표에 해당하는 melt배열의 값을 1로 표시하자.

map의 모든 칸을 이중 for문으로 돌면서, 

값이 1인 칸을 만났을 때, 그 좌표의 사방을 조사해서, 

2방면 이상 공기이면, melt배열에 해당 좌표의 값을 1로 표시.

map의 모든 칸을 이중 for문으로 돌면서,

값이 1인 칸을 만났을 때, 그 좌표의 사방을 조사해서,

2방면 이상 공기이면,     // 내부의 공기에 대해서는 영향을 미치면 안됨. 즉, 외부공간과 내부공간을 구분해야함!

큐에 해당 좌표를 저장해서. 하루가 지난 후(day++ 한 후),

큐에서 하나씩 꺼내면서 해당 위치의 map값을 0으로 바꾸기.

다른풀이)

# 1.

(1) dfs로 외부 공기부분을 모두 탐색하면서 -1 저장.

사방을 조사하여, 치즈(1)와 맞닿아 있으면, 맞닿은 치즈의 값을 +1시켜줌.

// 모든 탐색이 끝난 후, 두면 이상 외부공기와 맞닿아있는 치즈부분의 값은 3 이상이 되어있을것임.

(즉, map에서 

값이 -1이면, 외부공기.

값이 0 이면, 내부공기.

값이 1 이면, 내부 치즈.

값이 2 이면, 한면만 공기와 접촉한 치즈.

값이 3 이상이면 두면 이상 공기와 접촉한 치즈.)

(2) 따라서, 2중포문 돌려서 

값이 3 이상인 부분을 전부 0으로 바꿔줌(녹았다는 뜻).

값이 -1 인 부분은 전부 0으로 원래대로 돌려줌.

 && 하루가 지났으니 day++;

# 2.

(1) dfs로 외부 공기부분을 모두 탐색하면서 값을 2로 초기화.

(2) 2중 for문으로 map의 모든 칸을 돌면서 값이 1(치즈)인 칸을 만났을 때, 

그 좌표의 사방을 조사하여, 두 면 이상이 외부공기(2)와 접촉해 있으면, 해당 치즈의 값을 +1 시켜줌.

// 이제, 두방면 이상 맞닿은 치즈부분의 값은 3 이상이 되어있을 것임.

(즉, map에서

값이 0 이면, 내부공기.

값이 1 이면, 내부치즈

값이 2 이면, 한면만 공기와 접촉한 치즈 && 외부 공기. 

값이 3 이상이면 두면 이상 공기와 접촉한 치즈.)

(3) 이중 for문으로 map의 모든 칸을 돌면서 3 이상인 부분을 전부 2로 바꿔줌(녹았다는 뜻.)

 && 하루가 지났으니 day++;

(2), (3) 반복.