#1113 수영장 만들기

출처:https://www.acmicpc.net/problem/1113

1113번: 수영장 만들기

 

문제

지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다.

 

16661

61116

16661

 

이 수영장은 15만큼의 물이 들어있는 수영장을 만들 수 있다. 가운데 3개의 칸에 5만큼 물을 채우면 되기 때문이다.

자 이제 가운데 물을 더 추가했다고 생각하면, 벽(높이가 6인 직육면체)을 넘어서 밖으로 나갈 것이다. 물은 항상 높이가 더 낮은 곳으로만 흐르고, 직육면체 위의 표면에는 물이 없다. 그리고, 땅의 높이는 0이고, 땅은 물을 무한대로 흡수 할 수 있다.

땅의 모양이 주어질 때, 수영장에 물이 얼마만큼 있을 수 있는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 땅의 높이가 주어진다. 높이는 1보다 크거나 같고, 9보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 문제의 정답을 출력한다.

 

풀이

문제를 풀기 위해 총 2개의 함수를 만들었다. 물의 높이를 2~9까지 채울 때 그때 상황마다 맵에 물을 채워주는 simul함수, 물을 채울 수 있는 곳과 채울 수 없는 곳에 그룹을 지어주는 bfs함수를 만들었다.

simul함수를 실행시키고 그 안에서 bfs를 통해 그룹을 지어주고 나서 이중 for문을 통해 맵 전체를 보면서 이제 물을 채울 수 있는 그룹이면 1.해당 좌표를 현재 물 높이로 변경하고 2 ans(채운 물의 양)값을 올려준다. 만약 물을 채울 수 없는 그룹이면 해당 좌표의 물높이만 현재 물높이로 바꿔주기만 하면 된다.

 

코드