[백준 2638 C++] 치즈

치즈 문제 링크 (백준(BOJ) 2638번 문제): https://www.acmicpc.net/problem/2638

2638번: 치즈

문제 풀이 

백준 2638번 치즈 문제는 흔히 BFS (Breadth First Search) 알고리즘을 사용하는 문제이다. 이 문제에서 주목할 점은 치즈의 내부와 외부를 구분하는 것이 핵심이었다. 그리하여, 쓴이는 MAP을 돌면서 0인 부분에서 BFS를 시행하여 각각의 (치즈가 없는)공간을 번호로 나눠주었고 여러 공간들 중에 BFS 수행 시 범위를 벗어나는 값이 있다면 벡터에 저장해준 후 나중에 비교해주었다. 

위 예제를 보면, 치즈 조각이 없는 공간이 총 3개로 구분될 수 있는데, 이것 영역들 중에서 BFS 수행 시 ( y < 0 || y >= R || x < 0 || x >= C) 범위에 접근하는 영역은 치즈의 외부 영역이라고 인식하였다. 

 

그리하여, 이를 코드로 나타내면 아래와 같이 나타낼 수 있다.