[백준] 2638번: 치즈 (C++ 풀이)

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

풀이

1. 문제에서 가장자리 칸은 치즈를 두지 않는다고 했으니, (0,0)에서 BFS를 시작해서 상하좌우에 치즈칸이 있으면 그 치즈칸의 vis배열값을 +1해준다.

-> (0,0)에서 시작하는 이유는 치즈의 외부와 내부를 구분하기 위함이다. 그래서 치즈의 가장자리만 탐색하기 위함이다.

 

2. arr배열값이 1이고(치즈칸) vis배열값이 2이상인 것들만 arr배열값을 0으로 바꾼다. -> 치즈 녹이기 작업

 

3. vis배열을 0으로 초기화하고 arr배열에 1이 다 사라질때까지 반복한다.

 

코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/2638.cpp

결과

처음에 치즈의 내부와 외부를 구분하기 위한 BFS와 치즈칸이 바깥공기와 인접하는 변이 몇 개인지 탐색하는 BFS를 따로 돌렸더니 메모리초과가 났다.