[백준] 1113 수영장 만들기

www.acmicpc.net/problem/1113

1113번: 수영장 만들기

20202-12-26

---

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main1113 {
    public static int N, M, answer, maxHeight, arr[][];
    public static boolean check;
    public static Queue<int[]> q;
    public static boolean vtd[][];
    public static int dx[] = {-1, 0, 1, 0};
    public static int dy[] = {0, -1, 0, 1};
        
    public static void init() {
        for(int i = 0; i < N; i++) 
            for(int j = 0; j < M; j++)
                vtd[i][j] = false;
    }
    
    public static int solve(int value) {
        int size = 1;
        while(!q.isEmpty()) {
            int tmp[] = q.poll();
            int x = tmp[0];
            int y = tmp[1];
            
            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx < 0 || ny < 0 || nx > N-1 || ny > M-1) {
                    check = true; //하나라도 가장자리에 닿게 되면 물을 부을 수가 없다.
                    continue;
                }
                else if(!vtd[nx][ny] && arr[nx][ny] < value){
                    vtd[nx][ny] = true;
                    q.add(new int[] {nx,ny});
                    size++;
                }
            }
        }
        if(check) size = 0; //만들수가 없기때문에 초기화
        return size;
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
 
        answer = 0;
        maxHeight = -987654321;
        arr = new int[N][M];
        vtd = new boolean[N][M];
        q = new LinkedList<>();
        
        for(int i = 0; i < N; i++) {
            String str = sc.next();
            for(int j = 0; j < M; j++) {
                arr[i][j] = Character.getNumericValue(str.charAt(j));
                if(maxHeight < arr[i][j]) maxHeight = arr[i][j];
            }
        }
 
        for(int p = 2; p <= maxHeight; p++) {
            init();
            for(int i = 1; i < N-1; i++) {
                for(int j = 1; j < M-1; j++) {
                    check = false;
                    if(arr[i][j] < p && !vtd[i][j]) { //p의 높이보다 낮은 높이이면서 방문한 적이 없는 칸
                        vtd[i][j] = true;
                        q.add(new int[] {i, j});
                        answer += solve(p);
                    }
                }
            }
        }
        
        System.out.println(answer);
    }
}
 

developmentspace.tistory.com/65

[백준] 1113번 : 수영장 만들기

마지막에 계속 '틀렸습니다'가 나와서 결국 이 블로그를 참고하여 풀었다.

 

 

#문제풀이

 

1. 입력값을 받을 때, 가장 높은 높이를 미리 체크해주었다. 어차피 수영장의 높이는 그 높이 이상으로 높아질 수가 없다고 생각했다.

2. 높이를 2부터 입력 값에서 구한 가장 높은 높이까지 한 칸씩 물의 높이를 늘려가면서 체크해준다. 현재 칸의 물의 높이가 체크하고 싶은 물의 높이보다 작으면서 방문한 적이 없는 경우 bfs로 구역을 체크하게 된다.

+) 이 때, check라는 변수를 하나만드는데, 이는 bfs를 돌 때 가장자리를 돌았는지 안 돌았는지 체크해주는 변수이다. bfs를 돌면서 만약 하나라도 가장자리에 닿게 된다면, 물을 부을 수가 없으므로, 범위를 벗어나게 된다면 check = true를 해준다. (이 부분을 체크를 안 해줘서 답이 맞지 않았었다.)

3. 방문한적이 없거나 현재 칸의 물 높이가 체크하고 싶은 높이보다 작은 경우, 하나의 구역으로 생각한다.

4. bfs가 끝나고 나서 check가 true인 경우 size를 0으로 만든다.