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

[Gold I] 수영장 만들기 - 1113

문제 링크

성능 요약

메모리: 12768 KB, 시간: 88 ms

분류

너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현, 시뮬레이션

제출 일자

2024년 6월 10일 23:52:11

문제 설명

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

16661
61116
16661

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

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

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

입력

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

출력

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

 

접근 방법

1. 가장 낮은 높이와 가장 높은 높이를 입력시 저장하여 범위를 설정하여 높이별로 확인한다..

2. 각 칸들을 모두 확인하여 해당 높이를 가진 칸을 증가시킨다(BFS).

3. 이 때 테두리와 연결된 칸들은 증가 시키지않음(테두리와 연결된 칸은 물을 채울 수 없음)

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 {
    static class Point {
        int x;
        int y;

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


    static Queue<Point> queue = new LinkedList<>();
    static int[][] pool;
    static int N, M;

    static int[] dirX = {-1, 0, 1, 0};
    static int[] dirY = {0, -1, 0, 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());
        pool = new int[N][M];

        // Input
        // 시작 범위와 종료 범위
        int s = 10, e=0;
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < M; j++) {
                pool[i][j] = input.charAt(j) - '0';
                if (s > pool[i][j]) {
                    s = pool[i][j];
                }
                if (e < pool[i][j]) {
                    e = pool[i][j];
                }
            }
        } // Input End

        int answer = 0;
        // 현재 높이 h에서 채울 수 있는 모든 칸 탐색
        for (int h = s; h <= e; h++) {
            // 테두리는 물이 될 수 없으므로 제외하고 계산한다.
            for (int i = 1; i < N - 1; i++) {
                for (int j = 1; j < M - 1; j++) {
                    if (pool[i][j] == h) {
                        answer += bfs(h, i, j);
                    }
                }
            }
        }
        System.out.println(answer);
    }

    private static int bfs(int depth, int x, int y) {
        queue.add(new Point(x, y)); // 현재 위치 대입
        pool[x][y] = depth + 1; // 현재 위치에 1증가
        boolean isPossible = true; // 더 할 수 없는지 체크하는 변수
        int count = 1; // 더한 물의 개수

        while(!queue.isEmpty()){
            Point cur = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nX = cur.x + dirX[i];
                int nY = cur.y + dirY[i];

                // 테두리는 물을 채울 수 없으므로 제외하고 내부의 칸들만 탐색
                if (!isIn(nX, nY) || pool[nX][nY] < depth) {
                    isPossible = false;
                    continue;
                }
                if(pool[nX][nY] == depth){
                    pool[nX][nY] = depth + 1;
                    count++;
                    queue.add(new Point(nX, nY));
                }
            }
        }
        return isPossible ? count : 0;
    }

    private static boolean isIn(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }
}