백준 1113번 수영장 만들기 문제 해설, 그림으로 한방에 이해시켜 드림!

백준 1113번 수영장 만들기 문제 해설

문제 링크

solved.ac 기준 플레 5 난이도의 문제입니다. bfs 를 사용하여 해결하였으며 일반적인 2차원 bfs 문제와 달리 3차원 bfs 로 접근해야 하므로 어느정도의 구현능력이 필수적인 문제였습니다. 풀이에 대한 구체적인 설명이 있는 블로그도 없어서 이 글을 작성했습니다. 직접 그린 그림으로 한방에 이해시켜 드립니다!

문제

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

16661
61116
16661

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

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

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

입력

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

출력

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

예제입력

3 5
16661
61116
16661

예제출력

15

문제 풀이

우선 가장 간단하고 직관적으로 바로 떠오르는 방법부터 생각해보겠습니다.

수영장의 가장 낮은 바닥부터 한 층 씩 물을 채운후, 각 층마다 벽이 뚫려있어 물이 흘러내리는 칸을 확인하여 물을 없앤다

위의 아이어가 수영장에 물을 채우는 가장 직관적인 방법일 것 입니다. 저도 처음에 이 방식 부터 접근하였습니다. 하지만, 이 아이디어를 기반으로 밑에서 위로, 수영장에 물을 한층 채우고, 물이 흘러내리는 칸에는 물을 없애주는 방식으로 코드를 구현해보았을때, 구현 상에 어려운 부분이 있었습니다. 밑의 그림들을 보시죠.

문제의 입력을 단순화 시켜서 시각화 해보았습니다. 오른쪽의 표는 수영장의 바닥의 높이 이며 왼쪽의 회색 블록들은 주어진 입력인 표 (2D) 를 입체도 (3D) 로 시각화 하였습니다.

1층에는 바닥밖에 없으므로 물을 채울 공간이 없습니다. 1층 다음인 2층에 물을 채워줍니다. 하늘색 블록이 채워진 물을 나타냅니다.

문제에 주어진 조건에 따라서, 수영장의 가장자리 에는 물이 채워질 수 없으므로, 물이 흘러내리는 가장자리들의 물을 제거해 줍니다.

이제 다음 층인 3층에 물을 채워 봅시다. 이때 제가 겪은 문제점이 발생하게 됩니다. 3층에 물이 공중부양을 하고 있습니다.. 이는 2층의 물을 미리 제거한 후 3층에 물을 채웠기 때문입니다.

애초에 우리는 한층, 한층 물을 채우고 물이 흘러내리는 칸을 체크하여 제거하는 방법으로 이 문제를 해결하려고 했습니다. 이는, 각 층마다 물을 채우고 제거하는 과정이 독립적으로 성공되야 하는데, 위의 그림에서 2층에서 물을 채우고 제거하는 과정으로 인해 3층의 물이 공중부양하게 되는 문제가 발생하게 됩니다.

물이 공중부양 하고 있는 경우는 애초에 상상하지도 않았고, 의도하지도 않았죠! 따라서 이러한 접근방식으로 코드를 작성하게 되면 공중부양하고있는 물을 어떻게 처리할 것인가 에 대한 로직이 추가적으로 들어가게되고, 이에따라 소스코드가 복잡하고 거대해집니다.. 바로 제가 그랬습니다!

따라서, 조금 다른 방식으로 문제를 접근해 보겠습니다.

문제 접근 방식

우리가 앞서 살펴봤던 한층, 한층 물을 채우고 물이 흘러내리는 칸을 체크하여 제거하는 방법 의 문제점은, 물이 공중부양 하고있는 문제였습니다. 물이 공중부양 했던 이유는, 물은 아래로 흘러내리는데 물을 채우는건 아래에서 위로 채웠기 때문입니다. 따라서 전에 채웠던, 밑의층이 물이 사라지는 경우가 발생했던 것 입니다.

따라서, 조금 다르게 접근해보겠습니다.

물을 처음에 수영장에 가득 채워놓은 후에, 맨 윗층부터 밑으로 물을 제거하면 어떨까?

이러한 방식을 사용하면, 물이 공중부양하는 경우가 없어집니다! 왜냐하면, 물을 가득 채운후에 맨 윗층부터 아래로 내려오면서 한층 한층 제거해 가기 때문에, 아직 제거하지도 않은 밑의층의 물에 없어질 가능성은 0 입니다.

그림으로 보다 확실하게 살펴보겠습니다.

우리가 생각한 방법대로, 물을 우선 수영장에 가득 채워봤습니다! 수영장에서 가장 낮은 층은 1층이고 가장 높은층은 3층 이므로, 결과적으로 수영장에 물을 우선 가득 채워보면 모두 높이가 3층 이 되겠네요. 그때의 수영장의 상태는 왼쪽 그림과 오른쪽 표 에서 확인할 수 있습니다.

이전 방법과는 반대로, 이제 맨 윗층부터 물이 흘러내는 칸을 확인하여 물을 제거해 보겠습니다. 이때, 맨 윗층에서 아랫층 까지, 한층 마다 독립적으로 물을 제거해 가도록 하겠습니다.

맨 윗층의 물을 제거하기 전 입니다.

맨 윗층의 물을 제거한 후 입니다. 물이 수영장의 가장자리에 있거나, 사방이 벽으로 막혀있지 않은 경우에 물은 흘러내리므로 이 조건에 해당하는 칸의 물을 제거하였습니다. 이제 밑의 칸으로 이동하여 이 과정을 반복해봅시다.

2층의 물을 제거하기 전 입니다.

2층의 물을 제거한 후 입니다. 마찬가지로 물이 수영장의 가장자리에 있거나, 사방이 벽으로 막혀있지 않은 경우에 물은 흘러내리므로 이 조건에 해당하는 칸의 물을 제거하였습니다.

이제 맨 밑층이네요. 제거할 물이 없습니다.

따라서, 최종적으로 물을 채울수 있는 칸은 2칸 이 됩니다.

이제 좀 감이 오셨나요? 문제 접근 방식을 다시 정리해보겠습니다.

물을 처음에 수영장에 가득 채워놓은 후에, 맨 윗층부터 밑층까지 한층 한층 물이 흘러내리는 칸을 체크하여 제거한다.

물이 흘러내리는 칸은 물이 수영장 가장자리에 존재하거나, 사방이 벽으로 막혀있지 않은 칸에 물이 존재할 경우 이다.

이제 우리는 문제를 풀 수 있는 접근 방식과, 물이 흘러내리는 칸의 조건을 알게 되었습니다.

물론, 제가 접근했던 방식처럼 한층 한층 2차원 bfs 로 물을 제거하는 것 이 아닌, 물을 가득 채워놓은 후 맨 윗층에서 3차원 bfs 로 맨 밑층까지 한번의 bfs로 물을 제거하는 방식도 있습니다! 하지만, 3차원 bfs 로 구현해본 결과 구현 난이도가 아이디어에 비해 급격하게 높아져서, 익숙하고 구현도 쉬운 2차원 bfs 를 사용하였습니다.

이제 남은건 아이디어와 접근방식을 소스코드로 옮기는 것 뿐 입니다!

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

int map[50][50];
int water[50][50];
bool visited[50][50];

int row, col;
int max_height = 0;
int min_height = 99;

int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

void bfs(int x, int y, int height)
{
	queue<pair<int, int>> q;
	q.push({ x, y });

	visited[x][y] = true;

	while (q.empty() == false)
	{
		int curx = q.front().first;
		int cury = q.front().second;
		q.pop();

		// 물을 한칸 제거
		water[curx][cury]--;

		for (int i = 0; i < 4; i++)
		{
			int nx = curx + dx[i];
			int ny = cury + dy[i];

			if (visited[nx][ny])
				continue;

			if (nx == 0 || nx == row - 1 || ny == 0 || ny == col - 1)
				continue;

			// 현재 층 에서 물이 이 칸에 차있고, 흘러내리는 경우
			if (map[nx][ny] + water[nx][ny] == height && water[nx][ny] > 0)
			{
				q.push({ nx, ny });
				visited[nx][ny] = true;
			}
		}

	}
}


void solve()
{
	for (int h = max_height; h > min_height; h--)
	{
		// 한층 한층 마다 독립적으로 물을 제거하기 위해 visited배열을 층마다 초기화
		memset(visited, false, sizeof(visited));

		for (int i = 1; i < row - 1; i++)
		{
			for (int j = 1; j < col - 1; j++)
			{

				// 현재 칸에 물이 있고, 아직 제거하지 않은 경우
				if (water[i][j] > 0 && !visited[i][j])
				{
					for (int l = 0; l < 4; l++)
					{
						int nx = i + dx[l];
						int ny = j + dy[l];

						// 현재 칸 보다 옆의 칸이 더 낮아서 물이 흘러내리는 경우
						if (map[nx][ny] + water[nx][ny] < map[i][j] + water[i][j])
						{
							bfs(i, j, h);
							break;
						}
					}
				}

			}
		}
	}

	// 맨 윗층부터 밑층까지 물을 제거해 준 후 남은 물의 양을 계산
	int result = 0;

	for (int i = 1; i < row - 1; i++)
	{
		for (int j = 1; j < col - 1; j++)
		{
			result += water[i][j];
		}
	}
	cout << result << endl;

}

int main()
{
	cin >> row >> col;

	for (int i = 0; i < row; i++)
	{
		string s;
		cin >> s;

		for (int j = 0; j < col; j++)
		{
			map[i][j] = s[j] - '0';
			water[i][j] = 0;

			if (max_height < map[i][j])
				max_height = map[i][j];

			if (min_height > map[i][j])
				min_height = map[i][j];
		}
	}

	// 수영장에 물을 가득 채웁니다
	for (int i = 1; i < row - 1; i++)
		for (int j = 1; j < col - 1; j++)
			water[i][j] = max_height - map[i][j];

	solve();
	return 0;
}

문제의 접근방식과 아이디어, 물을 제거하는 조건을 그대로 소스코드로 구현하였습니다. 물을 제거하는 조건을 구현하는 부분이 조금 복잡하므로 유심히 봐주시길 바랍니다.

문제풀이 후기

사실 이문제는 제가 3일 넘게 고민했던 문제입니다!

특히 물을 채우는 방향, 물이 흘러내리는 조건, bfs를 2차원을 사용할 것 이냐 3차원을 사용할 것 이냐 에 대해서 하나하나 구현해보면서 정말 많이 해맸습니다.

bfs와 3차원 이 합쳐진 이런 문제는 한번 그려보고 접근 방식을 뒤집거나 거꾸로 생각해보는게 많은 도움이 되는것 같습니다.

그림으로 정말 쉽게 이해되게 설명하려고 노력해봣는데, 잘 이해 되셨나요?

읽어주셔서 감사합니다! 많은 도움이 되었길 바랍니다.