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

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

1113번: 수영장 만들기

 

풀이

 

1) 주어진 수영장 벽의 최대 높이 maxHeight  구하기

2) 1부터 maxHeight 까지 for문을 돌려서 수영장 벽의 높이와 같은 노드를 찾아낸다.

3) 해당 노드의 좌표에서 bfs 탐색을 한다.
  3-1) 물은 위에서 아래로만 흐른다. 따라서 현재 높이 h 보다 작거나 같은 노드를 탐색한다.
  3-2) 이때 지나간 경로를 Queue를 통해 저장해 놓는다. (path)
  3-3) 만약 탐색한 곳이 수영장의 맨 바깥 테두리라면 물이 수영장 밖으로 새어나온다는 뜻!
  3-4) 그렇지 않다면 방문한 노드들에는 물을 채울 수 있다는 의미이다.
  3-5) 이때 물의 높이는 탐색하며 만난 벽들 중 h보다 첫 번째로 높은 벽이다. (minHeight)

4) 물을 채울 수 있는 경우에 한하여 path의 모든 좌표에 물을 minHeight만큼 넣는다.

5) 탐색이 모두 종료되면 가장 처음의 배열과 비교하여 변동된 값의 총합을 출력한다.

 

 

주의사항

 

1) 무지성으로 모든 좌표에서 bfs를 돌리면 메모리초과가 난다. 물의 높이를 이용하여 스마트하게 풀자.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BJ_G1_1113_수영장만들기 {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static int R,C, map[][];
    static boolean isVisited[][];

    public static void main(String[] args) throws IOException {
        int answer = 0;

        input = new BufferedReader(new StringReader(src));
        tokens = new StringTokenizer(input.readLine());
        R = Integer.parseInt(tokens.nextToken());
        C = Integer.parseInt(tokens.nextToken());
        if(R < 3 || C < 3) {
            System.out.println(0);
            return;
        }
        int [][]origin = new int[R][C];
        map = new int[R][C];
        int maxHeight = 0;
        for(int r=0; r<R; r++){
            String line = input.readLine();
            for(int c=0; c<C; c++){
                origin[r][c] = line.charAt(c) -'0';
                map[r][c] = line.charAt(c) -'0';
                if(origin[r][c] > maxHeight){
                    maxHeight = origin[r][c];
                }
            }
        }

        for(int h=1; h<=maxHeight; h++){
            isVisited = new boolean[R][C];
            for(int r=1; r<R-1; r++){
                for(int c=1; c<C-1; c++){
                    if(map[r][c] == h && !isVisited[r][c]){
                        isVisited[r][c] = true;
                        bfs(h,r,c);
                    }
                }
            }
        }

        for(int r=1; r<R-1; r++){
            for(int c=1; c<C-1; c++){
                answer += map[r][c] - origin[r][c];
            }
        }

        System.out.println(answer);
    }

    private static void bfs(int h, int r, int c) { // 물이 밖으로 새는지. 안샌다면 나보다 큰놈중에 젤작은놈을 찾는다.
        Queue<Node> queue = new LinkedList<>();
        Queue<Node> path = new LinkedList<>();
        queue.offer(new Node(r, c));
        path.offer(new Node(r, c));
        boolean flag = false;
        int minHeight = Integer.MAX_VALUE;

        while(!queue.isEmpty()){
            Node front = queue.poll();
            if(front.r == 0 || front.c == 0 || front.r == R-1 || front.c == C-1) { // 물샌다!!
                flag = true;
            }

            for(int d=0; d<4; d++){
                int nr = front.r + dr[d];
                int nc = front.c + dc[d];

                if(isIn(nr,nc) && !isVisited[nr][nc]){
                    if(map[nr][nc] <= h){
                        isVisited[nr][nc] = true;
                        queue.offer(new Node(nr, nc));
                        path.offer(new Node(nr, nc));
                    }else{
                        if(minHeight > map[nr][nc]){
                            minHeight = map[nr][nc];
                        }
                    }
                }
            }
        }
        if(flag) return;

        while(!path.isEmpty()){
            Node front = path.poll();
            map[front.r][front.c] = minHeight;
        }
    }

    static int dr[] = {0,0,-1,1};
    static int dc[] = {-1,1,0,0};

    static class Node{
        int r;
        int c;

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static boolean isIn(int r, int c){
        return (r>=0 && c>=0 && r<R && c<C);
    }
    static String src =
            "9 13\n" +
                    "1111111111111\n" +
                    "1555555555551\n" +
                    "1511111111151\n" +
                    "1511199911151\n" +
                    "1511192911151\n" +
                    "1511199911151\n" +
                    "1511111111151\n" +
                    "1555555555551\n" +
                    "1111111111111";
}

 

 

후기

 

솔직히 아직도 첫번째 풀이가 왜 메모리초과가 나왔는지 모르겠다.

첫번째 풀이는 다음과 같다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer tokens;
    static int R,C, map[][], origin[][], answer;
    static boolean isVisited[][];

    public static void main(String[] args) throws IOException {
        tokens = new StringTokenizer(input.readLine());
        R = Integer.parseInt(tokens.nextToken());
        C = Integer.parseInt(tokens.nextToken());
        if(R < 3 || C < 3) {
            System.out.println(0);
            return;
        }
        origin = new int[R][C];
        map = new int[R][C];
        for(int r=0; r<R; r++){
            String line = input.readLine();
            for(int c=0; c<C; c++){
                origin[r][c] = line.charAt(c) -'0';
                map[r][c] = line.charAt(c) -'0';
            }
        }

        for(int r=1; r<R-1; r++){
            for(int c=1; c<C-1; c++){
                isVisited = new boolean[R][C];
                bfs(r,c);
            }
        }

        for(int r=0; r<R; r++){
            for(int c=0; c<C; c++){
                answer += map[r][c] - origin[r][c];
            }
        }

        System.out.println(answer);
    }

    private static void bfs(int r, int c) { // 물이 밖으로 새는지. 안샌다면 나보다 큰놈중에 젤작은놈을 찾는다.
        Queue<Node> path = new LinkedList<>();
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(r, c));
        path.offer(new Node(r, c));
        isVisited[r][c] = true;
        int min = Integer.MAX_VALUE;
        while (!queue.isEmpty()){
            Node front = queue.poll();
            for(int d=0; d<4; d++){
                int nr = front.r+dr[d];
                int nc = front.c+dc[d];
                if(!isIn(nr, nc)) return; // 물이 새는 경우
                if(!isVisited[nr][nc]){
                    if(map[nr][nc] <= map[r][c]){
                        isVisited[nr][nc] = true;
                        queue.offer(new Node(nr,nc));
                        path.offer(new Node(nr,nc));
                    }else{
                        if(map[nr][nc] < min){
                            min = map[nr][nc];
                        }
                    }
                }
            }
        }
        while(!path.isEmpty()){
            Node front = path.poll();
            map[front.r][front.c] = min;
        }
    }

    static int dr[] = {0,0,-1,1};
    static int dc[] = {-1,1,0,0};

    static class Node{
        int r;
        int c;

        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static boolean isIn(int r, int c){
        return (r>=0 && c>=0 && r<R && c<C);
    }
}

 

 문제에서 주어진 메모리 제한은 128MB이다.

int형 은 4 바이트 이므로

128MB = 128 * 1024KB = 128 * 1024 * 1024B = int형 128 * 1024 * 1024 / 4개 = 33554432 이다.

즉 3천3백만 개의 int를 쓰는것이 가능하다.

위의 코드에서 Node 클래스는 int 형을 2개 가지고 있다. 따라서 1600만개의 Node 를 쓸 수 있다.

그럼 내가 Node를 1600만 개 썼나?

수영장의 크기는 50*50 = 2500 이고 같은 좌표를 중복 탐색하는 경우도 수영장 높이의 한계인 9를 넘지 못한다.경로 저장용 Queue를 따로 두었다고 해도 50*50*9*2 인데 왜 메모리 초과가 나는걸까?