[백준] 1113번 : 수영장 만들기 - 자바(JAVA)

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

1113번: 수영장 만들기

 

 

문제 해석

지민이는 수영장을 만드려고 합니다.

수영장을 만들 곳의 크기는 N*M의 직사각형입니다.

각, 칸에는 높이가 쓰여 있습니다.

 

16661
61116
16661

이 수영장에는 물이 15만큼 들어갈 수 있습니다.

높이가 6인 벽들로 둘러쌓여있는 부분인 가운데 3개의 칸에 5만큼 물을 채울 수 있습니다.

 

땅의 모양이 주어질 때, 수영장에 물이 얼마큼 있을 수 있는지 구하세요

높이는 항상 1보다 크거나 같고, 9보다 작거나 같습니다.

문제 풀이 전 설계

N,M의 범위가 작기 때문에 시간 복잡도를 크게 고려하지 않아도 될 것 같습니다.

문제의 핵심은 각 칸이 둘러쌓였는지 잘 검사해야 합니다.

만약 4방 탐색을 하여 해당 칸이 배열밖이라면 해당칸에는 절대 물을 넣을 수 없습니다.

만약 해당칸이 배열 안에 위치한다면 연결된 칸들을 모두 탐색합니다.

이때 주변에 연결된 칸들을 검사하다 보면 해당 칸이 배열 밖과 인접한 칸을 만날 수 있습니다.

 

어떤 칸에 물을 넣을 수 있을까?

1. 배열 테두리보다 작은 값을 가진다면 물을 넣을 수 있습니다.

 

 

어떤 칸에는 물을 넣을 수 없을까?

1. 배열 테두리에 존재한다면 물을 넣을 수 없습니다.

2. 배열 테두리보다 큰 거나 같은 값을 가진다면 물이 흘러내려서 넣을 수 없습니다.

3. 값을 9를 가진다면 절대 물을 넣을 수 없습니다.

 

아이디어 

N x M = 8 x 7 인 배열을 예시로 들어보겠습니다.

아이디어의 핵심은 테두리부터 한 단계식 줄어들면서 검사하는 것입니다.

배열 테두리의 최솟값보다 크거나 같은 값을 가진다면 물이 흘러서 넣을 수 없는 아이디어에서 시작되었습니다.

 

초기의 테두리 최솟값은 가장 작은 값인 1로 할당합니다.

 

1. 처음에는 테두리를 가장 외각의 테두리의 최솟값을 구합니다. (0,0)을 포함하는 테두리

2. 1~9까지의 숫자를 무작위로 부여해봤는데 여기서 최솟값은 1입니다.

3. 주의할 점은 (0,0) , (0,8) , (7,0), (7,8)에 들어가는 값은 영향을 주지 않습니다.

 

4. 이제 가장 외각 테두리에서 최솟값(1)을 구했으니 한 단계 안쪽의 테두리를 검사합니다. (1,1)을 포함하는 테두리

5. 모든 값들이 1보다 크거나 같으므로 해당 테두리에는 물이 채워질 수 없습니다.

6. 또한 이때의 최솟값은 4입니다. (최솟값이 커지는 경우에만 갱신합니다.)

 

7. 이제 다시 한 단계 안쪽의 테두리로 들어갑니다. (2,2)를 포함하는 테두리

8. 이때는 테두리의 값들을 비교하며 4보다 작은 값이 존재하면 물을 채워 넣습니다.

9. 물을 채워 넣으면서 테두리의 최솟값을 갱신합니다. 여기서 최솟값은 1입니다.

10. 하지만 최솟값이 4 -> 1으로 작아지므로 갱신하지 않습니다. (왜냐하면 3이라는 값이 들어오더라도 4라는 테두리 안에 속하기 때문에 물이 채워질 수 있습니다.

 

11. (3,3)인 테두리에 도착했습니다. 

12. 종료 조건이므로 물을 채울 수 있다면 채우면서 종료합니다.

 

종료 조건은 M/2 == 현재 X좌표 또는 N/2 == 현재 Y좌표입니다.

 

 

 

배열의 조작을 통해 구현하려고 했지만 각 끝점의 겹치는 부분도 빼주어야 했고 만약 최종적으로 내부에 위의 그림과 같은 1x3 같은 배열을 만나게 되었을 때 중복 값을 고려하거나 배열 outofIndex를 고려해줘야 했기 때문에 까다로웠습니다.

 

따라서 bfs처럼 4방 탐색을 하면서 x, y좌표의 유횻값을 체크하면서 테두리를 탐색합니다.

 

위의 방법은 반례가 있어 실패하였습니다.

 

48 40
1666116661166611666116661166611666116661
6111661116611166111661116611166111661116
1666116661166611666116661166611666116661
1666116661166611666116661166611666116661
6111661116611166111661116611166111661116
1666116661166611666116661166611666116661
1666116661166611666116661166611666116661
6111661116611166111661116611166111661116
1666116661166611666116661166611666116661
1666116661166611666116661166611666116661
6111661116611166111661116611166111661116
1666116661166611666116661166611666116661
1666116661166611666116661166611666116661
6111661116611166111661116611166111661116
1666116661166611666116661166611666116661
1666116661166611666116661166611666116661
6111661116611166111661116611166111661116
1666116661166611666116661166611666116661
1666116661166611666116661166611666116661
6111661116611166111661116611166111661116
1666116661166611666116661166611666116661
1666116661166611666116661166611666116661
6111661116611166111661116611166111661116
1666116661166611666116661166611666116661
1666116661166611666116661166611666116661
6111661116611166111661116611166111661116
1666116661166611666116661166611666116661
1666116661166611666116661166611666116661
6111661116611166111661116611166111661116
1666116661166611666116661166611666116661
1666116661166611666116661166611666116661
6111661116611166111661116611166111661116
1666116661166611666116661166611666116661
1666116661166611666116661166611666116661
6111661116611166111661116611166111661116
1666116661166611666116661166611666116661
1666116661166611666116661166611666116661
6111661116611166111661116611166111661116
1666116661166611666116661166611666116661
1666116661166611666116661166611666116661
6111661116611166111661116611166111661116
1666116661166611666116661166611666116661
1666116661166611666116661166611666116661
6111661116611166111661116611166111661116
1666116661166611666116661166611666116661
1666116661166611666116661166611666116661
6111661116611166111661116611166111661116
1666116661166611666116661166611666116661

output : 4020

 

풀이는 다음 블로그를 참고하였습니다.

https://haejun0317.tistory.com/157

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

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_1113_수영장만들기 {

    static class Pos {
        int y;
        int x;

        public Pos(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    static final int MAX = 52;
    static int[][] arr = new int[MAX][MAX];
    static int n, m, maximum, ans;
    static Queue<Pos> q;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        String temp;
        for (int i = 1; i <= n; i++) {
            temp = br.readLine();
            for (int j = 1; j <= m; j++) {
                arr[i][j] = Character.getNumericValue(temp.charAt(j - 1));
                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;
                    }
                }
            }

        }
        System.out.println(ans);
    }


    private static void bfs(int h) {
        q = new LinkedList<>();
        arr[0][0] = h;
        q.add(new Pos(0, 0));
        while (!q.isEmpty()) {
            Pos currentPos = q.poll();
            int y = currentPos.y;
            int x = currentPos.x;

            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.add(new Pos(ny, nx));
                }
            }
        }
    }

    private static boolean inside(int y, int x) {
        return y >= 0 && y <= n + 1 && x >= 0 && x <= m + 1;
    }
}