풀이 방법
파도에 깎일 수 있는 곳을 찾아서 큐에 넣어주고 각 시간마다 한번에 변화시켜준다.
만약 모래가 없어진다면 없어진곳 주변만 다시 비교해서 파도에 깎일 수 있는 곳인지 찾아주었다.
내 코드
package com.company;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[][] way = {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}};
static int[][] arr;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int H = Integer.parseInt(st.nextToken());
int W = Integer.parseInt(st.nextToken());
boolean[][] visited = new boolean[H][W];
arr = new int[H][W];
int time = 0;
Queue<int[]> q = new LinkedList<>();
for (int i = 0; i < H; i++) {
String[] s = br.readLine().split("");
for (int j = 0; j < W; j++) {
if (s[j].equals(".")) {
arr[i][j] = 0;
} else {
arr[i][j] = Integer.parseInt(s[j]);
}
}
}
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (arr[i][j] != 0 && arr[i][j] != 9) {
if (arr[i][j] <= check(i, j)) {
visited[i][j] = true;
q.add(new int[]{i, j});
}
}
}
}
while (!q.isEmpty()) {
int size = q.size();
while (size-- > 0) {
int[] sand = q.poll();
int x = sand[0];
int y = sand[1];
arr[x][y] = 0;
for (int i = 0; i < 8; i++) {
int nx = way[i][0] + x;
int ny = way[i][1] + y;
if (!visited[nx][ny] && arr[nx][ny] != 0 && arr[nx][ny] <= check(nx, ny)) {
q.add(new int[]{nx, ny});
visited[nx][ny] = true;
}
}
}
time++;
}
System.out.println(time);
}
static int check(int i, int j) {
int count = 0;
for (int u = 0; u < 8; u++) {
int nx = i + way[u][0];
int ny = j + way[u][1];
if (arr[nx][ny] == 0) {
count++;
}
}
return count;
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
빵집 - 3109번 (0) | 2022.02.17 |
---|---|
가장 가까운 공통 조상 - 3584번 (0) | 2022.02.15 |
스타트링크 - 5014번 (0) | 2022.02.14 |
호텔 - 1106번 (0) | 2022.02.10 |
문제 추천 시스템 Version 1 - 21939번 (0) | 2022.02.10 |