boj)2573 - 빙산
2020. 10. 24. 12:39ㆍPS/boj
import java.io.*;
import java.util.*;
public class boj_2573 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N, M, nx, ny;
static int[][][] map;
static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M][2];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j][0] = Integer.parseInt(st.nextToken());
}
}
int year = 0;
while (true) {
int cnt = 0;
year++;
// 1년 단위로 빙산 주위에 바다 갯수 체크
for (int i = 1; i < N-1; i++) {
for (int j = 1; j < M-1; j++) {
if (map[i][j][0] > 0) {
cnt++;
for (int k = 0; k < 4; k++) {
nx = i + dx[k];
ny = j + dy[k];
if (map[nx][ny][0] == 0) {
map[i][j][1]++;
}
}
}
}
}
// 빙산이 없음
if (cnt == 0) {
System.out.println(0);
break;
}
// 주위의 바다 갯수만큼 빙산 높이 줄이기
for (int i = 1; i < N-1; i++) {
for (int j = 1; j < M-1; j++) {
if (map[i][j][0] > 0) {
map[i][j][0] -= map[i][j][1];
map[i][j][1] = 0;
}
if (map[i][j][0] < 0) map[i][j][0] = 0;
}
}
// 빙산 덩어리 갯수 카운팅
int ans = 0;
Stack<int[]> s = new Stack<>();
boolean[][] v = new boolean[N][M];
for (int i = 1; i < N-1; i++) {
for (int j = 1; j < M-1; j++) {
if (map[i][j][0] > 0 && !v[i][j]) {
v[i][j] = true;
s.push(new int[] {i, j});
ans++;
while(!s.isEmpty()) {
int[] now = s.pop();
for (int k = 0; k < 4; k++) {
nx = now[0] + dx[k];
ny = now[1] + dy[k];
if (map[nx][ny][0] > 0 && !v[nx][ny]) {
v[nx][ny] = true;
s.push(new int[] {nx, ny});
}
}
}
}
}
}
// 덩어리 수가 2개 이상일 경우
if (ans >= 2) {
System.out.println(year);
break;
}
}
}
}
- 이제 dfs/bfs에 어느정도 감이 오는것 같다.
- 다른 사람 코드 보니까 내 코드 길이는 거의 2배인거 같다 ..
- map을 map[N][M][2] 로 만들어서 마지막 배열쪽에 바다 갯수 카운팅을 저장했다.
'PS > boj' 카테고리의 다른 글
boj)13023 - ABCDE (0) | 2020.10.29 |
---|---|
boj)2206 - 벽 부수고 이동하기 (0) | 2020.10.24 |
boj)1629 - 곱셈 (0) | 2020.10.23 |
boj)2468 - 안전 영역 (0) | 2020.10.21 |
boj)10026 - 적록색약 (0) | 2020.10.21 |