[백준] 수영장 만들기 1113번 (java)

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

 

풀이 방법

경계를 판단하기가 어려웠고 높이가 1~9이기 때문에 범위가 매우 작다는 점을 이용해서 가장 작은 높이에서 가장 큰 높이 직전까지 1씩 증가해 가면서 풀이하는 방법으로 풀이했다.

(한 번에 계산은 안됨)

 

테두리일 경우, 넘쳐나게 되므로 테두리일 땐, 높이를 증가시키면 안 된다.

이를 위해 visited 값을 2로 설정한 것은 높이를 증가시키지 않았다.

또한 중복해서 더해지는 경우도 방지해야 하므로 한 번 높이를 증가시킨 경우 visited값을 +1을 해주어서 중복 계산을 방지해야 한다.

import java.io.*;
import java.util.*;


public class Main {
    static int n, m;
    static int[][] pool, visited;
    static int maxN, minN, ans = 0;
    static int[] dy = {0, 0, 1, -1};
    static int[] dx = {1, -1, 0, 0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        pool = new int[n][m];
        visited = new int[n][m];
        maxN = 0;
        minN = 9;
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0;j < str.length();j++) {
                pool[i][j] = str.charAt(j) - '0';
                maxN = Math.max(maxN, pool[i][j]);
                minN = Math.min(minN, pool[i][j]);
            }
        }
        // 각 수에서 bfs를 돌리며, 채울 수 있는지 없는지 판별한다 수가 된다면 큐에 넣고 bfs 만약 돌다 끝에 닿으면 다 패기한다.
        for (int i = minN; i < maxN; i++) {
            // visited 초기화 하기
            initViisted();
            for (int j = 1; j < n-1; j++) {
                for (int k = 1; k < m-1; k++) {
                    if (visited[j][k] != 0) continue;
                    if (pool[j][k] != i) continue; // i가 아니면 패스
                    bfs(j, k, i);
                }
            }
        }
        System.out.println(ans);
    }
    public static void bfs(int y, int x, int h) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {y, x});
        visited[y][x] = 1;
        boolean flag = true;
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            for (int i = 0;i < 4;i++) {
                int ny = cur[0] + dy[i];
                int nx = cur[1] + dx[i];
                if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
                if (visited[ny][nx] == 1) continue;
                if (pool[ny][nx] < h) flag = false;
                // 테두리라면 종료해야한다.
                if ((ny == 0 || nx == 0 || ny == n-1 || nx == m-1) && pool[ny][nx] <= h) {
                    flag = false;
                    continue;
                }
                // 주변에 나보다 작은 것이 있지만 처리가 되지 않은 것이 있다면 종료해야한다.
                if (pool[ny][nx] != h) continue;
                q.offer(new int[] {ny, nx});
                visited[ny][nx] = 1;
            }
        }
        if (flag) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (visited[i][j] == 1) {
                        pool[i][j]++;
                        ans++;
                        visited[i][j]++; // 중복해서 더해지지 않도록 하는 함수
                    }
                }
            }
        }
        else { // flag가 false일 때
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (visited[i][j] == 1) {
                        visited[i][j] = 2;
                    }
                }
            }
        }
        return ;
    }
    public static void initViisted() {
        for (int i = 0; i < n; i++) {
            Arrays.fill(visited[i], 0);
        }
    }

}