[ 백준 1113 ] 수영장 만들기 (C++)

[문제보기]

 

[해결과정]

 1. 입력 받을 때 0,0 부터가 아닌 1,1 부터 <=N, <=M 까지 입력 받기.

<사진> 입력 받는 곳은 가운데 빈칸에 들어감

 2. 입력 받을 때 최고 값을 max 변수에 저장한다.

 3. 1부터 max값 까지 for문을 돌린다. ---> for(int i=1; i<=max; i++)

  3.1 bfs(i) 실행

   3.1.1 bfs(i) 함수에서 (0,0)를 i값으로 변경하고 queue에 넣는다.

   3.1.2 bfs를 실행한다. (0,0) 값을 시작으로 i값보다 작으면 i값으로 변경한다.

<사진> bfs(1)을 실행한 결과

   3.1.3 맵을 돌면서 i값 보다 작은 값이 있다면, ans+=1 해주고, 해당 배열 값은 +=1 해준다.

<사진> bfs(1)을 돌고 맵을 돌며 확인

     3.1.4 위와 같은 과정을 반복한다. 겉의 테두리가 내부까지 침투하지 않는 이상..

<사진> 좌측 : 최대 3까지 했을 경우, 우측 : 최대 4까지 했을 경우..

 

[소스코드]

#include<iostream>
#include<queue>
using namespace std;
 
const int MAX = 52;
int arr[MAX][MAX];
 
int n, m;
 
// 물 높이 최대값
int maximum=0;
 
// 정답
int ans = 0;
 
struct coor {
    int y;
    int x;
};
queue <coor> q;
 
// 범위체크
bool inside(int y, int x) {
    return y >= 0 && y <= n + 1 && x >= 0 && x <= m + 1;
}
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
void bfs(int h) {
    arr[0][0] = h;
    q.push({ 0,0 });
    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();
 
        int ny, nx;
        for (int i = 0; i < 4; i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if (inside(ny, nx) && arr[ny][nx] < h) {
                arr[ny][nx] = h;
                q.push({ ny,nx });
            }
        }
    }
}
 
int main() {
 
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%1d", &arr[i][j]);
            if (arr[i][j] > maximum) maximum = arr[i][j];
        }
    }
 
    for (int o = 1; o <= maximum; o++) {
 
        bfs(o);
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (arr[i][j] < o) {
                    ans += 1;
                    arr[i][j] += 1;
                }
            }
        }
 
    }
 
    cout << ans << endl;
 
 
    return 0;
}

 

[해결 과정 중 실수한 부분]

 수영장은 내부에 1개만 있을 거라고 생각을 했다. 하지만, 수영장은 곧곧에 있을 수 있었다.

 

 

[관련 문제 혹은 비슷한 문제]

비슷한 문제 : 백준 2468 - 안전 영역