풀이 방법
dfs를 사용한 방법을 생각했다.
모두 다 이어져 있으면 다시 1년 지나게 하고 이어져 있지 않으면 종료하기 위해 먼저 빙산을 녹이는 함수를 작성했다.
주변을 비교해서 녹이면 되는 함수이다.
dfs는 check 배열을 만들어서 위치를 갔었는지 체크하고 0이 아닌 아무 곳에서 시작했다.
동서남북으로 확인하면서 가능한 경로인지 확인하고 연결되어 있는 갯수를 반환하게 했다.
내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
static int N;
static int M;
static int[][] array;
static int x, y;
static boolean[][] check;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
array = new int[N][M];
check = new boolean[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
array[i][j] = Integer.parseInt(st.nextToken());
}
}
int cnt = 0;
while (true) {
cnt++;
int count = 0;
if (!melt()) {
System.out.println(0);
break;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
check[i][j] = false;
if (array[i][j] != 0)
count++;
}
}
if (count != dfs(x, y)) {
System.out.println(cnt);
break;
}
}
}
static boolean melt() {
boolean check = false;
int[][] temp = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
temp[i][j] = array[i][j];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (array[i][j] != 0) {
if (array[i - 1][j] == 0) {
temp[i][j]--;
}
if (array[i + 1][j] == 0) {
temp[i][j]--;
}
if (array[i][j + 1] == 0) {
temp[i][j]--;
}
if (array[i][j - 1] == 0) {
temp[i][j]--;
}
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (temp[i][j] > 0) {
x = i;
y = j;
check = true;
array[i][j] = temp[i][j];
} else
array[i][j] = 0;
}
}
return check;
}
static int dfs(int x, int y) {
if (check[x][y]) {
return 0;
}
int cnt = 1;
check[x][y] = true;
if (array[x + 1][y] != 0)
cnt += dfs(x + 1, y);
if (array[x - 1][y] != 0)
cnt += dfs(x - 1, y);
if (array[x][y + 1] != 0)
cnt += dfs(x, y + 1);
if (array[x][y - 1] != 0)
cnt += dfs(x, y - 1);
return cnt;
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
어두운 건 무서워 - 16507번 (0) | 2021.10.15 |
---|---|
에너지 모으기 - 16198번 (0) | 2021.10.08 |
크게 만들기 - 2812번 (0) | 2021.10.07 |
짐 챙기는 숌 (0) | 2021.10.07 |
돌다리 건너기 - 2602번 (0) | 2021.10.06 |