[백준]10711: 모래성 - JAVA

[백준]10711: 모래성

10711번: 모래성

풀이

이 문제는! 직관적인 방법으로 생각해서 풀면 시간초과가 발생하는 문제이다.

 

우선, 대부분 첫번째로 떠오른 풀이 방법은 다음과 같을 것이다.

• 모든 노드의 탐색을 반복하며 모래성이 있는 노드 주변의 8방향 노드값을 확인하여 무너지는지, 무너지지 않는지 확인한다.

위의 방법으로 푼다면 테스트 코드는 통과되겠지만 시간 복잡도 측면에서 효율적이지 못하다. 매번 모든 노드를 탐색하는 방법 보다 더 효율적인 탐색 방법이 필요하다!

 

😣 모래성이 있는 노드를 중심으로 생각하는 것이 아닌, 모래성이 없는 노드를 중심으로 생각해 주어야 한다!

 

- 예를들어 아래와 같은 상황이 있다고 해보자. 

.	.	.
.	3 -> 2	.
.	.	.

맨 왼쪽 위의 좌표가 '.' 이며 이는 모래성이 없음을 의미한다. 모래성이 없으므로 주변 8방향의 노드 중에 모래성이 있는 노드의 튼튼함을 하나 깎아준다. (3 -> 2)

 

- 위의 경우에서 탐색을 진행하다 보면 결국엔 가운데 모래성이 없어지게 될 것이다. 이때는 그냥 해당 위치를 모래성이 없는 노드에 추가시켜 주기만 하면 도니다. 

 

이러한 방법으로 생각해 주면 매번 모든 노드를 탐색할 필요 없이 모래성이 없는 노드 주변만 확인하면 된다. 

이 마져도 이미 한번 확인한 모래성이 없는 노드는 다시 확인할 필요가 없으므로 새로 모래성이 없어진 노드만 탐색해 주면 된다.

 

❗ 새로 모래성이 없어지는 노드가 발생하지 않는 동안 탐색을 하면 그 시간이 우리가 구하고자 하는 정답이 될 것이다!

 

코드

import java.util.*;
 
public class Main {
 
    static int[] dx = { 0, 0, 1, 1, 1, -1, -1, -1};
    static int[] dy = { -1, 1, -1, 0, 1, -1, 0, 1};
    static int h, w;
    static char[][] board;
    static Queue<int[]> no_sand;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        h = scan.nextInt();
        w = scan.nextInt();
 
        board = new char[h][w];
        no_sand = new LinkedList<>();
        none = new boolean[h][w];
        for(int i = 0; i < h; i++) {
            String str = scan.next();
            for(int j = 0; j < w; j++) {
                board[i][j] = str.charAt(j);
                if(board[i][j] == '.') no_sand.add(new int[] {i, j});
            }
        }
 
        int count = 0;
        while(!no_sand.isEmpty()) {
            int size = no_sand.size();
 
            for(int i = 0; i < size; i++) {
                int[] current = no_sand.poll();
 
                for(int j = 0; j < 8; j++) {
                    int nx = current[0] + dx[j];
                    int ny = current[1] + dy[j];
                    if(nx >= 0 && ny >= 0 && nx < h && ny < w ) {
                        if(board[nx][ny] != '.') {
                            board[nx][ny]--;
                            if(board[nx][ny] == '0') {
                                board[nx][ny] = '.';
                                no_sand.add(new int[] {nx, ny});
                            }
                        }
                    }
                }
            }
            count++;
        }
        System.out.println(count - 1);
    }
}