[Algorithm] Baekjoon 1113번 : 수영장 만들기

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

1113번: 수영장 만들기

struct Node
{
    int y;
    int x;
};
 
 
int r, c;
int arr[51][51];
int water[51][51];
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
 
int maxHeight = 0;
int minHeight = 100;
int sum = 0;
bool visited[51][51] = { false };
int checkCount = 0;
 
bool isEdge(int y, int x)
{
    if (y == 0 || y == r - 1) // 맨 위 or 맨 아래
    {
        return true;
    }
    else if (x == 0 || x == c - 1)
    {
        return true;
    }
 
    return false;
}
 
void BFS(int startY, int startX)
{
    visited[startY][startX] = true;
    water[startY][startX] -= 1;
 
    queue<Node> q;
    q.push({ startY,startX });
    
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= r) continue;
            if (nextX < 0 || nextX >= c) continue;
            if (visited[nextY][nextX]) continue;
            if (water[nextY][nextX] == 0) continue;
 
            visited[nextY][nextX] = true;
            water[nextY][nextX] -= 1;
            q.push({ nextY,nextX });
        }
    }
}
 
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> r >> c;
    
    string input;
 
    for (int i = 0; i < r; ++i)
    {
        cin >> input;
 
        for (int j = 0; j < input.size(); ++j)
        {
            arr[i][j] = input[j] - '0';
            maxHeight = max(maxHeight, input[j] - '0');
            minHeight = min(minHeight, input[j] - '0');
        }
    }
 
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            water[i][j] = maxHeight - arr[i][j];
        }
    }
 
    int execCount = maxHeight - minHeight;
 
    while (execCount >= 1)
    {
        --execCount;
 
        memset(visited, false, sizeof(visited)); // 여기서 초기화
 
        for (int i = 0; i < r; ++i)
        {
            for (int j = 0; j < c; ++j)
            {
                if (isEdge(i, j) && !visited[i][j] && water[i][j] >= 1) 
                {
                    BFS(i,j);
                }
            }
        }
    }
 
    int sum = 0;
 
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            sum += water[i][j];
        }
    }
    
    cout << sum;
 
    return 0;
}

몇시간동안 풀이법생각하다가 다른분의 친절한 설명을 보고 해결할 수 있었다.

아이디어만 참고하고 코드는 직접 짜보도록 하자.

 

https://injae-kim.github.io/problem_solving/2020/02/15/baekjoon-1113.html

Injae's devlog

 

간단하게 말하자면, 물을 꽉채우고 위에서 하나씩 없애는 것이다.

처음 주어진 입력값으로 water라는 2차원배열에 각 칸마다 최대높이와의 차이를 저장한다.

그리고 이 water를 이용해서 맨 위에서 물을 한층씩 빼낼 것이다.

이 한층씩 빼내는 작업을 총 몇번수행할지는 maxHeight - minHeight값을 통해 결정된다.

 

우리가 수행할 BFS로직은 그저 조건에 맞는 water[i][j]값들에서 -1씩만 빼주는 것일 뿐이다.

그리고 시작지점은 반드시 외각에서만 시작한다.

물을 빼야한다는 것은 물이 샌다는 것이다. 즉, 외각에 벽이 없다는 것.

탐색을하면서 해당 water[i][j]값이 1이상이라는것은, 그 높이까지 물이 차올랐다는 것이다.

근데 외각에서 탐색을 시작했는데 1이상인값을 만났다는 것은, 결국 그 1이상인값과 외각은 연결되어있다는 것이고, 그건 반드시 물이 샌다는 것이다. (외각은 무조건 물이 샌다.)

그렇게 물이 새는것들에 대해서 water -= 1 코드를 통해 물을 빼주는 것이다. 

 

전체적인 시간은 꽤 걸렸지만, 그래도 추후에 도움이 될 것 같은 문제다.