[백준 / BOJ] 2638 치즈

문제

출처 : www.acmicpc.net/problem/2638

2638번: 치즈

N*M크기의 모눈종이에 치즈가 있다.

모눈종이의 가장자리부터 공기가 들어오는데, 공기에 2면 접촉해있는 치즈는 1초후 녹기시작한다.

 

가장자리에는 치즈가없을때, 모든 치즈가 녹아 없어지는데 걸리는 정확한 시간을 구하는 문제다.

 

풀이

BFS,DFS를 이용한 시뮬레이션 문제다.

N,M이 최대 100,100이라서 총 칸수가 10000칸 까지 갈수있다. 한번 치즈를 녹일때마다 모든 칸을 다 봐준다하면, 10000 * 10000 + a번 반복하여 시간초과가 날수도있기때문에, 조심히 구현해야했다.

 

치즈를 녹이는데 필요한 과정을 크게 2가지로 나눠서 생각했는데,

1. 가능한 모든 공간으로 공기를 주입한다. 이때 공기와 닿는 치즈를 q에 넣는다.

2. 치즈를 녹인다. 이때, 치즈의 2면 이상 공기와 닿아있는지 체크한다.

 

1번, 도착순서에 상관없이 모든경우를 다 봐줘야한다. 따라서 비교적 구현이 간단하고 코드가 짧은 DFS로 구현했다. 이때, 시간을 줄이기위해 공기를 주입하는 과정에서 치즈를 만난다면 해당 치즈를 q에 넣는다. (나중에 공기와 닿아있는 치즈를 찾기위해 한번더 반복할 필요없어짐) 

 

2번, q가 비어있다면, 치즈가없는것이므로 모든 치즈를 녹이는데 필요한시간을 출력하고 종료한다. 아니라면, q가 빌때까지 pop하며 사방중 2면이상 닿아있는지 체크한다. 2면이상 닿아있다면 해당칸을 0으로 바꾼다. 이때, 시간을 줄이기위해 q에 넣고 탐색해줬는데, 이렇게하면, 모든칸을 안보고 지워져야할 치즈가 있는칸만 확인할수있다. 

 

위 과정을 치즈가 모두 없어질때까지 반복하면 답이나온다. 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/2638%20%EC%B9%98%EC%A6%88/main.cpp

devxb/JJUNalgo