문제 이해 단계
https://www.acmicpc.net/problem/14719
2차원 맵이 주어진다.
이때 같은 층에 열로 가둬질 때 (위 그림처럼) 빗물을 담을 수 있다.
이 조건에서 2차원 맵의 크기가 주어지고,
각 행마다의 높이가 주어질 때 빗물의 총량을 구하는 문제이다.
문제 접근 단계
빗물의 총량을 구하기 위해서는 주어진 2차원 맵을 탐색 하면서
연산할 수 있는 일반화된 알고리즘이 필요하다고 생각했다.
그래서 일반화된 연산식을 만드는 것을 중점으로 생각했다.
첫 번째부터 쌓인 블록부터 탐색한다고 생각한다.
첫 번째 블록과 어떤 블록 사이에는 빗물이 쌓인다.
첫 번째 블록이 빗물을 담는 시작점이라고 생각(즉, 왼쪽 벽)하자.
그렇다면 첫 번째 블록과 쌍이 되는 오른쪽 벽은 어떻게 결정할까?
양쪽 그림 다 4번째 블록이 오른쪽 벽이 된다.
공통점은 왼쪽 벽의 블록 높이보다 크거나 같다는 것이다.
그리고 담기는 빗물 양의 높이는 왼쪽 벽의 높이보다 높을 수는 없다.
왼쪽 벽과 오른쪽 벽을 결정하는 방법으로 알고리즘을 구성할 수 있다.
일단 첫 번째 블록을 왼쪽 벽으로 지정한 다음,
블록을 순차탐색하다가 첫 번째 블록보다 크거나 같은 블록을 만나면 그 블록이 오른쪽 벽이 된다.
그러면 그 사이의 넓이만큼은 물이 담겨 있다고 가정하고
그 사이의 블록의 크기만큼 빼주는 것이다.
그림으로 나타내보면 이렇게 된다.
4번째 블록은 왼쪽벽과 높이가 같으므로 오른쪽 벽이 되고,
그 사이를 블록이 없다고 생각하고 최대 빗물양을 계산한다.
이후 원래 있던 블록을 빼주면 그 사이에 있는 빗물의 양을 계산할 수 있다.
이 계산 이후 4번째 블록을 다시 왼쪽 벽으로 지정해 주고 1번째 과정을 반복한다.
해당 그림에서는 5번째 블록이 바로 오른쪽 벽이 되어
그 사이에는 아무 블록도 없기 때문에 빗물 양은 0이 되고,
마지막 블록까지 왔기 때문에 탐색이 끝나게 된다.
이렇게 구현하면 끝일까? 그렇지 않다.
이 문제에는 큰 예외 케이스가 존재한다.
이렇게 된 경우를 생각해 보자. 분명 빗물의 양은 4이다.
그런데 해당 알고리즘으로 계산해 보면 답은 0이 된다.
왜냐하면 첫 번째 블록이 기준이 되어 오른쪽 벽을 찾을 텐데,
오른쪽 벽은 높이가 5 이상이어야 한다.
그런데 해당 그림에서는 존재하지 않기 때문에 오른쪽 벽을 찾지 못한다.
그래서 나는 해당 로직을 순차탐색했을 때, 오른쪽 벽을 찾지 못하면
해당 빗물 양을 저장해 놓고 역순으로 다시 한번 진행하였다.
순차탐색했을 때 빗물의 양은 0이고, 역순 탐색했을 때는 4이다.
즉 0+4 = 4로 알맞게 답이 나오는 것을 확인할 수 있다.
알고리즘을 정리하면 이렇다.
1. 첫 번째 블록은 왼쪽 벽으로 지정
2. 왼쪽 벽 높이보다 크거나 같은 블록을 찾을 때까지 순차 탐색한다.
3. 찾으면 그 벽을 오른쪽 벽으로 지정
4. 그 사이에 있던 공간 - 그 사이에 있던 블록 해서 빗물의 양을 구한다.
5. 오른쪽 벽을 왼쪽 벽으로 지정해서 마지막블록까지 1~4번을 반복한다.
6. 마지막이 오른쪽 벽인지 확인한다.(정상적으로 종료되었는지)
7. 오른쪽벽으로 끝나지 않았다면 역순으로 1~5번을 진행한다.
이제 이를 알고리즘으로 구현만 하면 된다.
문제 구현 단계
int finIdx; // 마지막 오른쪽 벽을 찾은 블록의 인덱스
int Cal(vector<int> block){
queue<int> q; // 사이 블록 담는 큐
int start = block[0];
int offset = 0; // 최대값에 오프셋
int water = 0;
for(int i = 1; i < block.size(); i++){
if(start > block[i]) {
q.push(block[i]);
offset++;
}
else{
int value = offset * start;
while(!q.empty()){
value -= q.front();
q.pop();
}
water += value;
start = block[i];
finIdx = i;
offset = 0;
}
}
return water;
}위의 알고리즘에서 4번 로직을 하는 핵심 알고리즘이다.
매개변수로 블록 벡터를 받아서 그 벡터 리스트들을 계산한다.
첫 번째 리스트를 무조건 시작블록으로 한 후 위에서 설명했듯
크거나 같은 블록을 찾을 때까지 순차탐색한다.
시작블록보다 작은 블록은 모두 큐 안에 넣어둬 임시 저장해 둔다.
찾으면 offset*start로 빗물양의 최댓값을 구한다.
offset은 거리가 멀어질수록 담을 수 있는 빗물의 양 또한
비례하여 많아지기 때문에 넣어준 것이다.
그리고 그 값에 큐 안에 넣어놨던 값을 모두 빼줘 빗물의 양을 계산한다.
그리고 finIdx를 해당 인덱스로 지정해 준다.
이 과정을 반복한 후 빗물의 양을 반환한다.
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int finIdx; // 끝났을 때의 왼쪽 벽 인덱스
int Cal(vector<int> block){
queue<int> q; // 사이 블록 담는 큐
int start = block[0];
int offset = 0; // 최대값에 오프셋
int water = 0;
for(int i = 1; i < block.size(); i++){
if(start > block[i]) {
q.push(block[i]);
offset++;
}
else{
int value = offset * start;
while(!q.empty()){
value -= q.front();
q.pop();
}
water += value;
start = block[i];
finIdx = i;
offset = 0;
}
}
return water;
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
int H,W;
cin >> H >> W;
vector<int> block;
for(int i = 0; i < W; i++){
int v;
cin >> v;
block.push_back(v);
}
int ans = Cal(block);
if(finIdx == block.size()-1) {
cout << ans;
return 0;
}
vector<int> v;
for(int i = block.size()-1; i >= finIdx; i--) v.push_back(block[i]);
//왼쪽벽이 있던 지점까지 역으로 리스트를 구성함
ans += Cal(v);
cout << ans;
}전체 코드이다. 여기서 핵심으로 봐야 될 부분이 밑에 있는데 finIdx를 활용한 것이다.
finIdx는 마지막으로 찾은 오른쪽 벽의 인덱스이다.
만약 finIdx가 마지막 블록이라면 정상적으로 모든 탐색이 마지막까지 돌아간 것이므로 굳이 역순탐색이 필요 없다.
즉 바로 답을 출력해 주면 된다.
그렇지 않은 경우만, 마지막으로 오른쪽벽이 계산된 시점을 가져와서
마지막 블록에서 시작해서 오른쪽 벽까지로 구성된 벡터를 만든다.
그렇게 하면 역순으로 구성된 벡터가 만들어진다.
이걸 다시 Cal에 넣으면 역순 탐색을 하는 효과가 나온다.
이를 출력하면 답이 나오게 된다.
시행착오
구현 관련 문제는 많이 풀어보지 않아서 힘들었다.
처음에는 2차원 맵인 것을 보고 BFS로 풀어보려고 했는데,
오히려 그렇게 하니까 더 복잡했다.
그래서 이리저리 머리를 굴려보다가
그냥 계산식을 만들어보자 하고 이렇게 구성해 봤다.
그런데 역시 구현 문제다 보니 구현에서 많은 어려움이 있었다.
아이디어 생각보다는 구현에서의 에러가 정말 많이 떴던 것 같다.
어려웠던 부분은 순차탐색이 안 되는 예외케이스를 처리하는 방법이었다.
그냥 이걸 뒤집어서 역순으로 돌리니 중복된 값이 더해지는 경우도 있어서
머리를 싸매다가 이 방법으로 결국 해결했다.
게임을 만들면서 구현문제는 어느 정도 자신 있는 줄 알았는데
구현도 역시 많이 풀어봐야 할 거 같다.
근데 이 문제 그리디도 약간 섞여있는 거 아닌가?