자바(백준) 10711 모래성

오답 노트 & 새로 알게 된 점

이 문제는 전에 풀었던 불!과 비슷한 단계형 bfs 문제다.

파도가 한 번 칠 때마다 모래성을 부수고 완전히 온전한 상태가 될 떄까지 파도의 횟수를 구하는 것이다.

 

처음에 문제를 이해하는데 어려움이 있었다. 온전한 상태가 무슨 말일까?

아무리 파도가 쳐도 무너지지 않는 모래성이다.

9는 무조건 온전한 상태이며, 주위에 있는 9의 개수에 따라서 8, 7 등 다른 숫자들도 온전한 상태가 될 수 있다.

 

처음 문제 풀이

처음 문제를 풀 때는 bfs를 돌릴 때, 9나 . 이 아닌 숫자들을 다 넣어주었다

그리고 각각 위치에서 8방향으로 탐색한 뒤, 부숴질 모래성이면

nonstable 배열에 저장하여 위치를 저장한 뒤에 bfs가 끝나면 그 때 . 을 넣어주었다.

 

하지만 위와 같이 문제를 해결한다면, TLE가 난다.

왜 TLE가 나는지 아직까지 모르겠다...

 

정답 문제 풀이

큐에는 다음 파도에 부숴질 모래들만 넣은 다음에,

현재 위치에서 . 으로 바꿔준 뒤에 그 주변 8 방향을 탐색한다.

그리고 현재 위치가 . 으로 바뀜에 따라 다음 파도에 부숴질 모래성들을

큐에 넣어준 뒤 탐색하면 된다.

 

이 문제도 단계별 bfs로 현재 큐 사이즈만큼 반복문을 돌리면 된다.

 

처음에 왜 방문처리가 필요하지라는 생각을 했다.

N이 이미 부숴진다고 큐에 들어가있는데

M이 . 로 바뀌면서 N이 부숴질 수 있다고 한다.

그러면 N이 큐에 또 들어가있으므로 중복처리를 해주기 위해 

방문처리를 사용하게 된다.

---

코드

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int row, col;
    static char A[][];
    static boolean visit[][];
    static int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int dy[] = {0, 1, -1, -1, 1, 0, 1, -1};
    static Queue<Integer> q = new ArrayDeque<>();
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        //제일 처음에 없어질 모래성 큐에 넣기
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(A[i][j] == '.' || A[i][j] == '9') continue;
                if(!check(i,j)){
                    q.offer(i);
                    q.offer(j);
                    visit[i][j] = true;
                }
            }
        }
 
        System.out.println(bfs());
    }
 
    static int bfs() {
        int time = 0;
        while(!q.isEmpty()) {
            int size = q.size();
 
            for (int i = 0; i < size / 2; i++) {
                int X = q.poll();
                int Y = q.poll();
 
                A[X][Y] = '.';
 
                for (int j = 0; j < 8; j++) {
                    int dX = X + dx[j];
                    int dY = Y + dy[j];
 
                    if(!isRangeTrue(dX,dY)) continue;
                    if(visit[dX][dY]) continue;
                    if(A[dX][dY] == '.') continue;
 
                    if(!check(dX,dY)){
                        q.offer(dX);
                        q.offer(dY);
                        visit[dX][dY] = true;
                    }
                }
            }
            time++;
        }
        return time;
    }
 
    static boolean check(int x, int y) {
        int cnt = 0;
 
        for (int i = 0; i < 8; i++) {
            int X = x + dx[i];
            int Y = y + dy[i];
 
            if(!isRangeTrue(X,Y)) continue;
            if(A[X][Y] == '.') cnt++;
        }
 
        return A[x][y] - '0' > cnt;
    }
 
    static boolean isRangeTrue(int x, int y) {
        return x >= 0 && x < row && y >= 0 && y < col;
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        row = atoi(st.nextToken());
        col = atoi(st.nextToken());
 
        A = new char[row][col];
        visit = new boolean[row][col];
 
        for (int i = 0; i < row; i++) {
            String str = br.readLine();
            for (int j = 0; j < col; j++) {
                A[i][j] = str.charAt(j);
            }
        }
    }
}