[백준/JAVA] 10711번: 모래성

📖 문제

10711번: 모래성

 

 

 

💡  풀이 방식

• BFS

. 모래성이 없는 노드를 중심으로 생각한다!

 

모래성이 없는 노드의 주변 8방향 노드 中 모래성이 있는 노드의 튼튼함을 하나 깎는다.

그러다 보면 결국 가운데 모래성이 없어지게 되는데, 이 때는 그 위치를 노드에 추가해주면 된다.

 

 

💥 유의사항

이미 한 번 확인한 모래성이 없는 노드는 다시 확인할 필요가 없기 때문에

새롭게 모래성이 없어진 노드만 탐색한다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dr = {-1,1,0,0,-1,-1,1,1};
    static int[] dc = {0,0,-1,1,-1,1,-1,1};
    
    static int H,W;
    static char[][] board;
    static Queue<int[]> q = new ArrayDeque<>(); // 모래성이 없는 위치 저장 리스트
    static int answer = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());
        
        board = new char[H][W];
        
        for(int i = 0 ; i < H ; i++) {
            String str = br.readLine();
            for(int j = 0 ; j < W ; j++) {
                board[i][j] = str.charAt(j);
                
                if(board[i][j] == '.') {    // 모래성이 없는 위치 저장!!
                    q.add(new int[] {i, j});
                }
            }
        }
        
        bfs();
        System.out.println(answer -1);
    }
    
    private static void bfs() {
        while(!q.isEmpty()) {
            int size = q.size();
            
            for(int i = 0 ; i < size ; i++) {    // 제한: 큐 사이즈만큼 🔥
                int[] now = q.poll();
                
                for(int d = 0 ; d < 8 ; d++) {  // 모래성이 없는 노드의 주변 8방향 탐색
                    int nr = now[0] + dr[d];
                    int nc = now[1] + dc[d];
                    
                    if(nr >= 0 && nr < H && nc >= 0 && nc < W) {
                        if(board[nr][nc] != '.') {  // 모래성이라면, 튼튼함 하나 깎기
                            board[nr][nc]--;
                            
                            if(board[nr][nc] == '0') {  // 💥 새로 모래성이 없어진 노드만 탐색!!
                                board[nr][nc] = '.';
                                q.add(new int[] {nr, nc});
                            }
                        }
                    }
                }
            }
            answer++;
        }
    }
}
 

 

 

 

 

➕ 다른 풀이 방식

헐 내가 풀려고 했던 방식은 이거였다!!!

[백준] 10711 :: 모래성 (BFS)

 

---

💦 어려웠던 점

- 모래성이 있는 점들을 중심으로 8방향 탐색하고, 주변의 모래가 없는 칸 수를 세서 이 친구를 제거하고 이러면서 풀려고 했는데 틀렸다. (이런 해결법도 분명 있긴 하다)

 

 

🧐 새로 알게 된 내용

- 큐 사이즈만큼 .의 갯수만큼 8방향 탐색하는 거

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[백준]10711: 모래성 - JAVA