728x90
2573번 / 빙산
❓ 빙산
🏷️ 관련 주제 : topic1 topic2 topic3
💦 나의 시도
Try01. 반복문을 이용한 방법
내가 시도한 코드
import java.io.*;
import java.util.*;
public class Main {
public static void main (String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 행 수
int M = Integer.parseInt(st.nextToken()); // 열 수
int[][] map = new int[N][M];
int[][] meltingSpeed = new int[N][M];
int[][] copyMeltingSpeed = new int[N][M];
ArrayList<String> iceberg = new ArrayList<>();
for (int i = 0; i < N; i++) {
map[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
for (int j = 0; j < M; j++) {
if (map[i][j] > 0) {
String ice = i + " " + j;
iceberg.add(ice);
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] != 0) {
int seaCnt = 0;
if (i - 1 >= 0 && map[i - 1][j] == 0) {
seaCnt++;
}
if (j - 1 >= 0 && map[i][j - 1] == 0) {
seaCnt++;
}
if (j + 1 < M && map[i][j + 1] == 0) {
seaCnt++;
}
if (i + 1 < N && map[i + 1][j] == 0) {
seaCnt++;
}
meltingSpeed[i][j] = seaCnt;
copyMeltingSpeed[i][j] = seaCnt;
}
}
}
int time = 0;
while (!iceberg.isEmpty()) {
ArrayList<String> copyIceberg = new ArrayList<>(iceberg);
for (String loc : copyIceberg) {
int[] index = Arrays.stream(loc.split(" ")).mapToInt(Integer::parseInt).toArray();
int row = index[0];
int col = index[1];
int ice = map[row][col];
int melt = meltingSpeed[row][col];
if (melt == 4) {
System.out.println(time);
return;
}
ice = Math.max(0, ice - melt);
map[row][col] = ice;
if (ice == 0) {
iceberg.remove(loc);
if (row - 1 >= 0 && map[row - 1][col] > 0) {
copyMeltingSpeed[row - 1][col]++;
}
if (col - 1 >= 0 && map[row][col - 1] > 0) {
copyMeltingSpeed[row][col - 1]++;
}
if (col + 1 < M && map[row][col + 1] > 0) {
copyMeltingSpeed[row][col + 1]++;
}
if (row + 1 < N && map[row + 1][col] > 0) {
copyMeltingSpeed[row + 1][col]++;
}
}
}
for (int i = 0; i < N; i++) {
meltingSpeed[i] = copyMeltingSpeed[i].clone();
}
time++;
}
System.out.println(0);
}
}❌ 틀렸습니다.
인터넷에서 찾은 반례로 테스트 해 보았는데 아래 테스트 케이스에 대하여 N, M을 입력 받는 부분에서 에러가 남
그런데 이유를 모르겠다.🥺
5 5
0 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 1 1 1 0
0 0 0 0 0
0제출해야할 시간이 다 되어서 일단 인터넷에서 찾은 풀이를 제출하였습니다.
📑제출 기록 및 오답 원인
💯 해결 방법
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class IceBerg {
int x;
int y;
IceBerg(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static int[] rangeX = { -1, 0, 1, 0 };
static int[] rangeY = { 0, 1, 0, -1 };
static int N, M;
static int[][] map;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
int ans = 0;
int cnt = 0;
// 빙하가 2개 이상 분리될 경우 반복문을 종료.
// 빙하가 다 녹아버렸을 경우, 0을 출력.
while ((cnt = SeparateNum()) < 2) {
if (cnt == 0) {
ans = 0;
break;
}
Melt();
ans++;
}
bw.write(ans + "\n");
bw.flush();
bw.close();
br.close();
}
// 빙하가 분리된 개수를 구하는 함수.
public static int SeparateNum() {
boolean[][] visited = new boolean[N][M];
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] != 0 && !visited[i][j]) {
DFS(i, j, visited); // DFS 방식을 통해 총 몇개의 빙하로 나누어졌는지 구할 수 있음.
cnt++;
}
}
}
return cnt;
}
public static void DFS(int x, int y, boolean[][] visited) {
visited[x][y] = true;
int dx, dy;
for (int i = 0; i < 4; i++) {
dx = x + rangeX[i];
dy = y + rangeY[i];
if (dx < 0 || dy < 0 || dx >= N || dy >= M) {
continue;
}
if (map[dx][dy] != 0 && !visited[dx][dy]) {
DFS(dx, dy, visited);
}
}
}
// 빙하를 녹이는 함수.
public static void Melt() {
Queue<IceBerg> q = new LinkedList<>();
// visited 배열을 만드는 이유
// visited 배열이 없다면,
// 만약 1 2 가 있는 상태에서 1이 먼저 녹아서 0이 될 경우
// 2는 녹아서 없어진 1 자리도 0이라고 판단하여
// 필요 이상으로 더 많은 값을 녹이게 되어 버림.
boolean[][] visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] != 0) {
q.offer(new IceBerg(i, j));
visited[i][j] = true;
}
}
}
int dx, dy;
while (!q.isEmpty()) {
IceBerg ice = q.poll();
int seaNum = 0; // 빙하 상하좌우에 존재하는 바다 영역의 수.
for (int i = 0; i < 4; i++) {
dx = ice.x + rangeX[i];
dy = ice.y + rangeY[i];
if (dx < 0 || dy < 0 || dx >= N || dy >= M) {
continue;
}
if (!visited[dx][dy] && map[dx][dy] == 0) {
seaNum++;
}
}
if (map[ice.x][ice.y] - seaNum < 0) {
map[ice.x][ice.y] = 0;
} else {
map[ice.x][ice.y] -= seaNum;
}
}
}
}🏷️ 문제 풀면서 참고한 블로그
728x90
