[BOJ] #2636 치즈

시간 제한	메모리 제한	정답 비율
1초	128MB	49.494%

2636번: 치즈

 

문제

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

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

 

해결

key point, DFS 활용!

1. 입력을 받으면서 치즈가 아닌 외각부분을 시작지점으로 저장해둔다.
2. dfs를 시작지점부터 시작하여 '공기와 접촉한 치즈 외각부분의 개수'를 리턴하여 cnt변수에 저장한다.
   동시에 공기와 접촉한 부분을 삭제했다는 의미로 arr배열 값을 0으로 바꿔준다.
3. dfs를 돌 때마다 time이 증가된다.
4. 한 시간 전에 남아있는 치즈조각의 개수를 알기 위하여 직전에 삭제한 치즈 조각 개수를 매번 ans에 저장해 두었고, cnt가 0일 때 반복문을 빠져나가 time과 ans을 출력하며 종료한다. 

 

코드

메모리	시간
2120KB	0ms