📖 문제
10711번: 모래성
첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이
www.acmicpc.net
💡 풀이 방식
• BFS
. 모래성이 없는 노드를 중심으로 생각한다!
모래성이 없는 노드의 주변 8방향 노드 中 모래성이 있는 노드의 튼튼함을 하나 깎는다.
그러다 보면 결국 가운데 모래성이 없어지게 되는데, 이 때는 그 위치를 노드에 추가해주면 된다.
💥 유의사항
이미 한 번 확인한 모래성이 없는 노드는 다시 확인할 필요가 없기 때문에
새롭게 모래성이 없어진 노드만 탐색한다.
🔺 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
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++;
}
}
}
|
cs |
➕ 다른 풀이 방식
헐 내가 풀려고 했던 방식은 이거였다!!!
[백준] 10711 :: 모래성 (BFS)
시간...초과의 늪에 빠져버렸던...이번 문제....ㅜㅜㅜㅜ 총 3 번의 갈아엎기 끝에 성공을 했다... 하얗게 ...
blog.naver.com
💦 어려웠던 점
- 모래성이 있는 점들을 중심으로 8방향 탐색하고, 주변의 모래가 없는 칸 수를 세서 이 친구를 제거하고 이러면서 풀려고 했는데 틀렸다. (이런 해결법도 분명 있긴 하다)
🧐 새로 알게 된 내용
- 큐 사이즈만큼 .의 갯수만큼 8방향 탐색하는 거
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V |
(참고)
[백준]10711: 모래성 - JAVA
[백준]10711: 모래성 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각
moonsbeen.tistory.com
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 1987번: 알파벳 (0) | 2024.04.18 |
---|---|
[백준/JAVA] 1455번: 뒤집기 II (0) | 2024.04.17 |
[백준/JAVA] 1726번: 로봇 (0) | 2024.04.13 |
[백준/JAVA] 5547번: 일루미네이션 (0) | 2024.04.12 |
[백준/JAVA] 17836번: 공주님을 구해라! (0) | 2024.04.11 |