Baekjoon 2636 치즈 JAVA

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

2636번: 치즈

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%202636

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 치즈의 위치가 주어지면 1초마다 경계면에 있는 치즈가 사라지는데

이때 모든 치즈가 사라지는 시간과, 마지막으로 사라지는 치즈의 수를 구하는 문제다.

조건으로는 치즈 안에 빈 공간이 있을 경우 해당 공간은 경계면으로 치지 않는다.

​

처음 문제를 보고 BFS를 이용해 경계면을 다 q에 넣어주고 줄이고 하면 되겠다고 생각했는데

조건이 있어서 생각을 해보다 보니 반대로 공기에서 시작해서 탐색하면서 만나는 치즈를

큐에다 넣어주고 이후 큐가 비지 않았으면 큐에 있는 내용을 가져와

해당 부분을 공기로 바꾸고 카운트한 뒤 다시 공기를 탐색하도록 하면 된다.

​

1. 공기부터 시작해서 탐색을 하고 공기를 만나면 공기 큐에, 치즈를 만나면 치즈 큐에 삽입

2. 공기를 다 탐색하면 치즈 큐가 비었는지 확인 비었으면 끝 안 비었으면 치즈 큐 탐색

3. 치즈 큐를 가져와서 해당 map을 공기로 바꿔주고 공기 쿠에 삽입 카운트를 증가

4. 시간을 증가시키고 위의 내용을 반복