[백준] 모래성 - JAVA

1. 문제

 

 

2. 접근

문제 읽고 평소에 풀던 BFS 문제들이랑 비슷해서 별로 생각 안하고 풀다가 시간초과가 났다.

 

접근1. 모든 좌표를 다 돌면서 모래성(1~9)인 경우 주변(대각선, 상하좌우)을 체크한 후 무너지면 체크해주기, 그리고 체크 된 모래성들을 한 번에 0으로 표시하기

 

이렇게 풀었더니 시간초과가 났다. 로직에는 문제가 없는 줄 알고 모든 좌표가 아닌 -> 모래성 좌표만 큐에 저장해서 찾아가는 식으로 바꿔봤다. 하지만 이 방법도 시간초과가 났다. 시간 복잡도를 구해보니 모래성의 크기가 1000X 1000 = 10^6(백만)이고, 모래성의 개수가 평균 50%라고 했을 때 50만이고 BFS니깐 한 파도가 칠 때 평균 50만 * (8방향)이고 파도가 약 (Max(H, W) 이니깐 약 400,000만... 40억 나오네. 시간초과가 날 수 밖에 없었다.

 

개선점을 찾다가 '영향을 받는 곳만 건들여 줘야하나? 영향을 받는 곳은 주변에서 모래성이 없어질 때 인데...이걸 어떻게 구현하지?' 하다가결국 못풀었다

 

접근2. 모래성이 아닌 곳을 체크하기

인터넷을 찾아보니 반대로 모래성이 아닌 곳을 체크하면서 주변에 모래성이 있는 경우 카운트를 1 감소시키는 방법이 있었다. 풀면서 아니 이 방법과 위 방법의 시간복잡도가 그렇게 차이 안나는데? 이건 왜 돼지 하면서 풀었는데 역시 이 방법도  시간초과가 났다. 

 

접근법만 보고 내 마음대로 구현했더니 역시 아니였다.

(차라리 다행이다. 풀면서 시간복잡도를 구했는데 둘 다 비슷해서, 이 방법이 됐으면 오히려 더 혼란일 뻔 했다)

 

핵심은 빈 모래성을 계속 탐색하는 것이 아니라 새롭게 빈 모래성이 된 것만 탐색해 나가는 것이었다. 

 

1. 우선 처음은 빈 모래성 좌표들을 큐에 담는다.
2. 그리고 하나씩 꺼내면서 주변에 모래성이 있으면 -1 해준다.
2-1. 모래성의 카운트가 0(빈 모래성)이 되면 큐에 넣어준다.
2-2. 모래성의 카운트가 1이상이라면 아직 아무일도 일어나지 않는다.
3. 큐가 빌 때까지 반복한다.

 

이 방법이 왜 되는지 처음엔 잘 이해하지 못했다. 지금도 완전히는 이해하지 못했다.

하지만 분석해보자면, 모래성이 없어질 때는 처음부터 주변에 빈 모래성 있거나, 주변에 새로운 빈 모래성이 생길 때이다. 그래서 굳이 매 번 기존 모래성을 가지고 주변 모래성을 확인하지 않아도 되는 것이다. 즉 하나의 빈 모래성은 한 모래성에게 오직 1번만 영향을 준다. 예를들어 (0,0)에 빈모래성이 있고, (1, 1)에 모래성이 있을 때 (0,0)에 의해 (1, 1)은 오직 튼튼함 1만 깎인다. (0,0)이 처음부터 있었든, 3초 뒤에 새롭게 생겼든 말이다. 그래서 큐에 새로운 빈 모래성만 넣어도 되는 것이다.

 

하지만 문제를 보면 마치 모래성을 가지고 주변 빈모래성을 한 번에 체크해야 될 것처럼 느껴진다. 이때까지 풀었던 많은 문제들이 그랬어서.... 아무튼 새로운 풀이법을 알게됐다!

 

 

3. 코드

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

class Main {

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        Queue<int []> noSand = new LinkedList<>();

        for(int i=0; i<N; i++){
            String str = br.readLine();
            for(int j=0; j <M; j++){
                if(str.charAt(j) == '.'){
                    map[i][j] = 0;
                    noSand.add(new int[]{i,j});

                }else{
                    map[i][j] = str.charAt(j) - '0';
                }
            }
        }

        // 시뮬
        int waveCount = 0;

        while(!noSand.isEmpty()){
            int size = noSand.size();
            boolean isChange = false;
            waveCount++;

            for(int i=0; i<size; i++){
                int [] cur = noSand.poll();

                for(int j=0; j<dr.length; j++){
                    int nr = cur[0] + dr[j];
                    int nc = cur[1] + dc[j];

                    if(nr <0 || nr >= N || nc <0 || nc >=M){
                        continue;
                    }
                    if(map[nr][nc] == 0){
                        continue;
                    }
                    map[nr][nc]--;

                    if(map[nr][nc] == 0){
                        noSand.add(new int[]{nr,nc});
                        isChange = true;
                    }
                }
            }
            if(!isChange){
                break;
            }
        }
        System.out.println(waveCount -1);
    }
}