[ 백준_BOJ ] 2636. 치즈 _ 문제풀이 JAVA

문제

 

 

 

 

 

 

풀이

 

 

#1.  Input( ) 부분

 

치즈가 있는 부분을 map 배열에 1로 표시해주었고 치즈 수를 세기 위해 cheese 변수를

1씩 ++해주었습니다.

 

 

#2.  Main 부분

 

Main에서는 while 문에서 치즈의 갯수가 0이 아닐 때까지 Melting( )과 Clear( ) 함수를

계속 반복합니다. 치즈가 모두 녹아서 사라지는 데 걸린 시간을 알기 위해 Time 변수를

while문을 실행할 때마다 1씩 늘려주었고, 모두 녹기 전에 ( Cheeze가 0이 되기 전 )

남아 있던 치즈의 갯수를 알기 위해 Ctmp 변수에  이전 치즈 값을 저장하였습니다.

 

 

#3.  Melting( ) 부분

 

이 문제에서 판의 테두리 'X' 부분에는 치즈가 위치하지 않습니다.

이를 이용하여 '치즈가 없는 바깥 부분, 또는 치즈가 녹아내려 사라진 부분'을 표시하기 위해

melt[ ] 배열을 이용하여 BFS로 ( 0, 0 ) 위치에서 탐색합니다.

 

또 Melting( ) 함수에서 처리해준 결과 값으로 다음 차례에 치즈가 녹는 부분들을 알아낼 수

있었습니다.

 

 

#4.  Clear 부분

먼저 녹아 내릴 치즈 부분을 isEdge( ) 함수를 이용하여 visited[ ] 배열에 표시합니다.

모두 검사한 이후에 치즈가 있는 위치라면 치즈를 지워주었습니다.

 

여기에서 주의할 점은 사라질 치즈 부분을 바로 제거해버린다면

안쪽에 있던 치즈들도 제거할 수 있으니 꼭 제거할 부분들을  먼저 체크해두었다가

확인이 끝난 후 제거해주셔야 문제 없이 코드가 수행됩니다.

 

 

 이 문제는 치즈를 없애주기 전에 사라질 부분들을 체크하고, 제거해주는 과정들을

분리해서 실행시킨다면 어렵지 않은 BFS 문제라고 생각됩니다.

 

치즈 안에도 구멍이 생길 수 있으므로 판의 가장자리에서 BFS로 바깥 부분과 안쪽 부분을

구분해내는 생각을 통해 풀이할 수 있었습니다.

 

 

 

코드

 

 

 

 

 

 

 

 

 

 

 

 

 

출처

 

 

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

2636번: 치즈