백준 1113 JAVA

문제 유형

• 시뮬레이션 + BFS

문제 접근

• 답
  • 물을 뿌릴 때 만들어지는 웅덩이의 용량
• 주어지는 정보
  • 맵 크기 최대 2500 (N * M)
  • 땅의 높낮이 1~9
• 후보
  • 완전탐색
    • 가능
    • 맵의 크기와 땅의 높낮이가 충분히 작음
    • 따라서, 문제 설명 그대로 시뮬레이션을 만드는 게 좋을 듯함
• 풀이(BFS)
  • 맵의 제일 낮은 땅, 높은 땅을 구한다.
  • 제일 낮은 땅들에 +1만큼의 물을 뿌린다.
  • 물을 뿌리고 난 후에 웅덩이가 형성될 시, 정답에 더한다.
  • 제일 높은 땅만큼 될 때까지 2번 과정에서부터 물을 +1 뿌린다.
• 주의
  • BFS()에서 웅덩이가 형성되지 않더라도, 물을 뿌려야한다(물을 뿌릴 수 있는 땅 한정).
  • 물을 뿌리지 않을 시, 물로 인해 높아진 땅이 벽처럼 형성돼서 새로운 웅덩이가 생길 수 있다.
  • 이는 가짜 웅덩이므로 count되면 안된다.

//맞는 접근
boolean TN = true;

.............

if(moveY<0 ||moveY >= N || moveX < 0 || moveX >= M || map[moveY][moveX] < height){
    TN = false;
    continue;
}

..............

if(TN == false) return 0;

//----------------------------------------------------------------------------

//틀린 접근
if(moveY<0 ||moveY >= N || moveX < 0 || moveX >= M || map[moveY][moveX] < height){
	//웅덩이 안 만들어지니 return 0
    return 0;
}

 

 

TN이 없을 시, 반례

5 5
11111
11121
11121
12121
11211

//정답 0
//출력 1

 

 

전체 코드

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

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

public class Main {
    static int N,M;
    static int[][] map;
    static int[][] move = {{1,0},{-1,0},{0,1},{0,-1}};
    
    public static int pourWater(int y, int x, int height){
        Queue<XY>q = new LinkedList<>();
        q.add(new XY(y,x));
        
        int point = 0;
        map[y][x] = height+1;
        point++;
        boolean TN = true;
        while(!q.isEmpty()){
            XY curXY = q.peek();
            q.remove();
            
            for(int i = 0; i<4; i++){
                int moveY = curXY.y + move[i][0];
                int moveX = curXY.x + move[i][1];
                
                
                if(moveY<0 ||moveY >= N || moveX < 0 || moveX >= M || map[moveY][moveX] < height){
                    TN = false;
                    continue;
                }

                if(map[moveY][moveX] != height){
                    continue;
                }

                point++;
                map[moveY][moveX] = height+1;

                q.add(new XY(moveY, moveX));
            }
        }
        
        if(TN == false) return 0;
        return point;
    }

    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());
        
        map = new int[N][M];
        
        int minHeight = 10;
        int maxHeight = 0;
        for(int i = 0; i<N; i++){
            String str = br.readLine();
            for(int j = 0; j<M; j++){
                map[i][j] = str.charAt(j) - '0';

                minHeight = Math.min(minHeight, map[i][j]);
                maxHeight = Math.max(maxHeight, map[i][j]);
            }
        }
        
        int point = 0;
        for(int height = minHeight; height<maxHeight; height++){
            for(int y = 1; y<N-1; y++){
                for(int x = 1; x<M-1; x++){
                    if(map[y][x] != height){
                        continue;
                    }
                    point += pourWater(y,x,height);
                }
            }
        }
        
        
        System.out.println(point);
    }
}

 

 

오답

• 접근
  • 시뮬레이션 + BFS
• 실패 이유
  • 메모리 초과
  • BFS 함수를 2번 사용함으로써, 메모리 초과 발생

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

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

public class Main {
    static int N,M;
    static int[][] map;
    static int[][] move = {{1,0},{-1,0},{0,1},{0,-1}};
    
    public static int checkOver(int y, int x, int height, boolean[][] visited){
        Queue<XY>q = new LinkedList<>();
        boolean[][] nextVisited = new boolean[N][M];

        q.add(new XY(y,x));
        nextVisited[y][x] = true;
        
        int maxHeight = Integer.MAX_VALUE;
        while(!q.isEmpty()){
            XY curXY = q.peek();
            q.remove();
            
            for(int i = 0; i<4; i++){
                int moveY = curXY.y + move[i][0];
                int moveX = curXY.x + move[i][1];
                
                
                if(moveY<0 ||moveY >= N || moveX < 0 || moveX >= M){
                    return -1;
                }
                
                if(nextVisited[moveY][moveX] == true){
                    continue;
                }

                if(map[moveY][moveX] > height){
                    maxHeight = Math.min(map[moveY][moveX], maxHeight);
                    continue;
                }
                
                nextVisited[moveY][moveX] = true;
                q.add(new XY(moveY, moveX));
            }
        }
        

        visited = nextVisited;
        return maxHeight;
    }
    
    public static int pourWater(int y, int x, int maxHeight){
        Queue<XY>q = new LinkedList<>();
        q.add(new XY(y, x));
        
        int point = 0;
        point += maxHeight - map[y][x];
        map[y][x] = maxHeight;
        
        while(!q.isEmpty()){
            XY curXY = q.peek();
            q.remove();
            
            for(int i = 0; i<4; i++){
                int moveY = curXY.y + move[i][0];
                int moveX = curXY.x + move[i][1];
                
                if(map[moveY][moveX] > maxHeight){
                    continue;
                }
                
                point += maxHeight - map[moveY][moveX];
                map[moveY][moveX] = maxHeight;
            }
        }
        
        return point;
    }

    public static void printMap(){

        System.out.println("----------printMap---------");
        for(int i = 0; i<N; i++){
            for(int j = 0; j<M; j++){
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    
    public static void printVisited(boolean[][] visited){

        System.out.println("----------printVisited---------");
        for(int i = 0; i<N; i++){
            for(int j = 0; j<M; j++){
                if(visited[i][j] == true){
                    System.out.print(1 + " ");
                }
                else{
                    System.out.print(0 + " ");
                }
            }
            System.out.println();
        }
    }

    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());
        
        map = new int[N][M];
        
        for(int i = 0; i<N; i++){
            String str = br.readLine();
            for(int j = 0; j<M; j++){
                map[i][j] = str.charAt(j) - '0';
            }
        }
        
        int cnt = 0;
        int point = 0;
        boolean TN = false;
        while(TN == false){
            boolean[][] visited = new boolean[N][M];

            cnt++;
            if(cnt == 2){
                int a= 3;
            }

            TN = true;
            for(int i = 0; i<N; i++){
                for(int j = 0; j<M; j++){
                    if(visited[i][j] == true){
                        continue;
                    }
                    
                    //printVisited(visited);

                    int height = map[i][j];
                    int maxHeight = checkOver(i,j,height,visited);
                    
                    if(maxHeight == -1){
                        continue;
                    }
                    
                    TN = false;
                    point += pourWater(i,j,maxHeight);
                    

                    //printMap();
                }
            }
        }
        
        
        System.out.println(point);
    }
}