[백준 / BOJ] 1113 수영장 만들기

문제

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

1113번: 수영장 만들기

N*M크기의 칸에 수영장을 만들려고 한다.

각 칸에 그 땅이 갖고있는 높이가 주어졌을때, 수영장에 물을 얼만큼 넣을수있는지 구하는 문제이다.

만약 수영장이 다음과 같다면,

 

16661

61116

16661

 

가운데 3개의칸에 5씩 넣어서 총 15만큼의 물을 넣을수있다.

만약 5보다 더 많이 넣는다면 수영장 벽의 높이인 6보다 커져서 물이 넘친다.

 

풀이

한달전에 풀었던 문제였다.

 

N*M이 최대 250 이고, 벽의 높이가 1~9라서

N,M이 최대일때 약 250 * 9 = 2250번 반복할것이다. (소스코드마다 다르겠지만..)

따라서 완전탐색으로 구현해도 시간초과가 나지않는다.

 
우선 N*M배열의 각 칸을 입력받을때, 칸의 최댓값을 저장해준다. (문제의 예제 1 에서는 6이 최댓값이 될것이다.)

그후, N*M배열의 칸의 높이가 1일때부터 저장해놓은 최댓값 까지 반복하며 칸을 채워 넣는다.

(이때, 옆의 벽이 뚫려있거나 채워넣는 물의 높이가 옆의 벽높이보다 커진다면 채워넣지않고 종료한다.)

 

예를들어, 배열이 

 

14441

41214

14441

 

이렇게 주어졌을때, 최댓값은 4이다. 위에서 말한것처럼 우선 칸의 높이가 1인지점을 전부 찾아서 물을 채워준다.

 

14441

42224

14441

 

이렇게 물이 채워질것이다. 이때, (1,1) (1,5) (3,1) (3,5)는 옆에 벽이 없기때문에 물을 넣을수없다.

그다음 높이가 2인 칸을 찾아서 물을 채워넣는다.

 

14441

43334

14441

 

마찬가지로 4일때 채워넣으면

 

14441

44444

14441

 

이렇게 채워지면서 결국 답은 8이된다. 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1113%20%EC%88%98%EC%98%81%EC%9E%A5%20%EB%A7%8C%EB%93%A4%EA%B8%B0/main.cpp

devxb/JJUNalgo