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

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

1113번: 수영장 만들기

 

 

이와 비슷한 문제를 카카오에서 본것같아서 반가웠다. 카카오 코딩 테스트 당시에는 풀지 못했던 문제라 이번 문제는 꼭 풀어야지 하는 마음이 있었다. 살짝 달랐던건 카카오는 1차원이고 이문제는 2차원 이라는 정도....?

 

여러 고민을 많이 했었다. 일일히 탐색하는 방법부터 하나씩 보는 방법까지 생각을 했는데, 토의해볼때 dfs로 풀수있다고 해서 의외로 간단한 문제였네 라는 생각이 들었다. 문제를 어떻게 간단하게 생각하고 작은 아이디어를 생각해 내는 힘이 진짜 중요한 것 같다. 같이 푼 스터디원의 이야기를 듣고, 같은방식이지만 나는 bfs방식을 선호해서 bfs방식으로 진행하였다.

풀이는 수영장의 가장자리 부분에는 정해진 높이에 따라 땅으로 흘러갈 수 있고 울타리가 될수도 있기 때문에 이를 구별하는 방법 찾으면 끝나는 문제이다.

찾기 쉽지 않았지만 방법을 듣는 순간 정말 똑똑하다는 생각이 들정도로 간단한 문제였다ㅜㅜ

 

 

방법은 간단하다. 

1. 주어진 수영장 전체 크기를 감싸는 가장 작은 높이의 땅을 만든다.

2. 탐색을 (0,0)에서 시작하면 설정한 높이보다 낮은 땅들에 물을 채운다.(높이는 1~9까지 한번씩 탐색)

3. 설정한 높이이상의 땅들은 물로 채워지지 않고, 그안쪽의 땅들도 채워지지 않는다. 

4.  채워지지않은 땅들을 체크하여 채워질수있는 물의 양에 합한다.

 

이정도이다.

주어진 수영장의 전체 크기를 감싸는 가장 작은 높이의 땅을 설정하는 것이 포인트 인것 같다.

 

이 아이디어만 생각해 내면 그렇게 어려운 문제는 아닌 것 같다.

(물론 이 아이디어를 떠올리는 힘이 진짜 실력인 것이지만.....ㅎ) 

 

[코드]

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<functional>
#include<queue>
#include<math.h>
#include<stack>
#include<string.h>
#include<cmath>
#include<map>
using namespace std;
int pull[55][55];
int X[4] = { 1,0,-1,0 };
int Y[4] = { 0,1,0,-1 };
int N, M;
void bfs(int limit) {
	queue<pair<int, int>>q;
	int ck[55][55] = { false };
	q.push({ 0,0 });
	pull[0][0] = limit;
	ck[0][0] = true;
	while (!q.empty()) {
		int prex = q.front().first;
		int prey = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = prex + X[i];
			int ny = prey + Y[i];
			if (nx >= 0 && nx <= N+1 && ny >= 0 && ny <= M+1 && !ck[nx][ny]) {
				if (pull[nx][ny] < limit) {
					pull[nx][ny] = limit;
					ck[nx][ny] = true;
					q.push({ nx,ny });
				}
			}
		}
	}
}
int main(void) {
	
	scanf("%d %d", &N, &M);
	int Maxlimit = 0;
	for (int i = 0; i <= N + 1; i++) {
		for (int j = 0; j <= M + 1; j++) {
			if (i == 0 || j == 0 || i == N + 1 || j == M + 1) {
				pull[i][j] = 1;
				continue;
			}
			scanf("%1d", &pull[i][j]);
			Maxlimit = max(pull[i][j], Maxlimit);
		}
	}
	int sum = 0;
	for (int limit = 1; limit <= Maxlimit; limit++) {
		bfs(limit);
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (pull[i][j] < limit) {
					
					sum += (limit - pull[i][j]);
					pull[i][j] = limit;
				}
			}
		}
	}
	printf("%d\n", sum);


	return 0;
}