BOJ_1113 : 수영장 만들기

👉 문제링크

---

---

🔸 문제 분석 🔸

• N x M 직사각형 땅에 수영장을 만든다. 격자 속 숫자가 해당 땅의 높이이다.
• 물을 채워야 하는데, 물은 상하좌우 높은 곳에서 낮은 곳으로만 흐르고 격자 밖으로는 무한정 흘러나가 버린다.
• 채울 수 있는 물의 양의 최대값을 출력한다.

🔸 문제 풀이 🔸

1. 상하좌우 인접 땅으로 흐르는 물의 이동을 구현하기 위해서 BFS를 사용한다.
2. 외각에 붙은 땅은 물이 고일 수 없으므로, 역방향 BFS를 통해 이어진 땅들을 모두 체크한다.
3. 물이 고일 수 있는 땅들에 물을 채우고 총합을 출력한다.
4. 물 높이의 최대값은 2가지 기준을 유의해서 정한다.
   1. 해당 높이보다 높아지면 물이 흘러나가버리는 경우 : 최대값의 인덱스가 체크된 경우
   2. 흘러나가지는 않지만, 땅이 높아서 조금 더 높이 물이 고이는 경우 : 최대값의 인덱스가 체크되지 않은 경우

🔸 코드 🔸

import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static final int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상하좌우
    private static int N, M;
    private static int[][] pool;
    private static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        pool = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            char[] chars = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                pool[i][j] = Character.getNumericValue(chars[j]);
            }
        }

        // BFS 1) 물을 부으면 안되는 곳은 true
        for (int i = 0; i < N; i++) {
            if (!visited[i][0]) {
                noWater_Upper(new Point(i, 0));
            }
            if (!visited[i][M - 1]) {
                noWater_Upper(new Point(i, M - 1));
            }
        }
        for (int i = 0; i < M; i++) {
            if (!visited[0][i]) {
                noWater_Upper(new Point(0, i));
            }
            if (!visited[N - 1][i]) {
                noWater_Upper(new Point(N - 1, i));
            }
        }

        // BFS 2) 채우는 물 양 카운트
        int cnt = 0;
        for (int i = 1; i < N - 1; i++) {
            for (int j = 1; j < M - 1; j++) {
                if (!visited[i][j]) {
                    cnt += cntPoolWater(new Point(i, j));
                }
            }
        }

        // Output
        bw.write(Integer.toString(cnt));
        bw.flush();
    }

    private static void noWater_Upper(Point start) { // 상승 방향으로 물을 못 담는 위치 표시
        Queue<Point> que = new ArrayDeque<>();
        que.add(start);
        visited[start.row][start.col] = true;
        while (!que.isEmpty()) {
            Point p = que.poll();
            for (int[] dir : dir) {
                int row = p.row + dir[0];
                int col = p.col + dir[1];
                if (0 <= row && row < N && 0 <= col && col < M
                        && !visited[row][col] && pool[row][col] >= pool[p.row][p.col]) {
                    visited[row][col] = true;
                    que.add(new Point(row, col));
                }
            }
        }
    }

    private static int cntPoolWater(Point start) { // 물이 고이는 최대 높이 반환
        int maxHeight = Integer.MAX_VALUE;

        Queue<Point> que = new ArrayDeque<>();
        Queue<Point> water = new ArrayDeque<>();
        boolean[][] flag = new boolean[N][M];

        que.add(start);
        water.add(start);
        flag[start.row][start.col] = true;

        while (!que.isEmpty()) { // 물 높이의 최대값 찾기
            Point p = que.poll();
            for (int[] dir : dir) {
                int row = p.row + dir[0];
                int col = p.col + dir[1];
                if (visited[row][col]) { // 물을 채우면 안되는 곳
                    if (pool[row][col] <= pool[p.row][p.col]) { // 채우면 안되는 곳인데 흘러감
                        noWater_Upper(new Point(row, col));
                        return 0;
                    }
                    maxHeight = Math.min(maxHeight, pool[row][col]);
                } else if (!flag[row][col] && pool[row][col] <= pool[p.row][p.col]) { // 시작 위치에 물 부우면 같이 참
                    flag[row][col] = true;
                    que.add(new Point(row, col));
                    water.add(new Point(row, col));
                } else if (pool[row][col] > pool[p.row][p.col])
                    maxHeight = Math.min(maxHeight, pool[row][col]);
            }
        }

        int cnt = 0;
        for (Point p : water) {
            if (maxHeight > pool[p.row][p.col]) {
                cnt += maxHeight - pool[p.row][p.col];
                pool[p.row][p.col] = maxHeight;
            }
        }

        return cnt;
    }

    private static class Point {
        int row, col;

        public Point(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

🔸 코드 해석 🔸

• N x M 땅의 테두리는 물이 흘러나가버린다. 물이 흘러 들어오는 땅들도 모두 물을 채우면 안되는 땅이므로 역방향 BFS를 구현한 noWater_Upper() 메서드를 통해 visited를 true로 체크한다.
• visited가 false인 나머지 땅들에 cntPoolWater() 메서드로 물을 채운다.
  • 시작 위치에서 같거나 작은 높이로 이어진 땅들을 water 큐에 넣는다.
  • 이때 주변 땅의 높이 중 가장 낮은 값을 max에 저장한다.
  • 탐색이 끝나면, water에 저장 된 땅들에 max 만큼 물을 채운다.

---

🔸 end 🔸

• 상당히 어려웠고 시간이 많이 걸린 문제이다. BFS를 2종류로 나눠서 하고 역방향으로 하면 되겠다는 아이디어는 금방 나왔는데, 구상을 조금 이상하게 해서 테케를 많이 만들었어야 했다.
• 물을 채우는 cntPoolWater() 메서드의 BFS에서 탐색 범위를 visited가 false 경우로만 뒀었는데, 땅의 높이가 갖거나 낮은 경우라는 조건도 추가로 필요했다.
• 한 번 탐색한 땅은 배제하려고 했던게 큰 오점이었는데, 같은 칸이어도 물을 여러번 높여가는 방식으로 바꾸어서 해결되었다.
• 코드 디버깅에 시간이 너무 걸려서 리팩터링은 포기하고 좀 지저분한 형태의 답안으로 마무리되었다...