백준 #1113 수영장 만들기

블럭으로 쌓아 만든 공간이 있습니다.  블럭 사이사이는 물이 들어가지 않는다고 할 때, 이 블럭위로 물을 충분히 부우면, 얼마만큼 많은 물이 담길까요?

 

이 문제는 수영장 만들기라는 제목이지만, 내용을 해석해서 간단하게 풀어 말하면 위와 같습니다.  백준 사이트 문제들을 풀다 보면, 프로젝트 오일러 문제와의 차이가, 문제 자체를 누가 명확하게 설명하는가입니다.  백준 사이트는 스토리를 강조하는 느낌들이 많고, 프로젝트 오일러 문제들은 문제 풀기에 집중하는 느낌입니다.

 

block pool

 

물이 담길려면, 어떤 블럭 A의 높이가 a 라면, 적어도 a+1 이상의 블럭들로 A를 포함한 집단 블럭들을 감싸고 있어야 합니다.  그러면 블럭 A에 물이 담길 수 있습니다.  간단하게 생각하면 쉬운 문제이지만, 이 문제는 Platinum V로 난이도가 꽤 높게 책정되어 있습니다.  정답률 26.7%로 그다지 높지는 않네요.

 

저는 나름 쉽게 풀었습니다.  DFS를 이용해서 풀었습니다.  높이가 1부터 9까지로 제한되어 있으므로, 1부터 시작해서 8까지 DFS로 탐색하면 됩니다.  총 있을 수 있는 블럭의 갯수는 50x50=2,500 개이므로,  DFS 알고리즘을 생각하면, \(O(NM)\) 으로 해결이 가능합니다.

 

여러 케이스 올려드립니다.

7 9
123454321
234515432
345121543
451232154
345121543
234515432
123454321
==> 46

1 1
1
==> 0

5 5
59995
95549
94449
95449
88888
==> 33

5 7
1234567
2345671
3456712
4567123
5671234
==> 2