백준 2636. 치즈

tose33 2022. 5. 12. 14:50

2636번: 치즈

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓

www.acmicpc.net

치즈 내부의 공간과, 치즈 외부의 공간을 구분하는 문제였다.

치즈 외부의 공간을 판별하는 법은 문제에서 힌트가 주어진다.

문제에서 판의 가장자리는 치즈가 존재하지 않는다고 주어졌으므로 판의 가장자리 아무데나 예를들어 (0,0)에서 부터 dfs나 bfs를 돌리면 치즈가 아닌 부분이 모두 치즈 외부 부분이고, 나머지 1은 치즈, 0으로 남아있는 공간이 치즈 내부이다.

따라서 매초마다

1. 치즈 외부 공간 판별

2. 치즈 가장 자리 삭제