[JAVA] 백준 5212_지구온난화

[문제링크]

https://www.acmicpc.net/problem/5212

📌 문제 탐색하기

해수면 상승에 따라서 섬의 일부가 잠기는 현상으로 인해서 50년 이후 변경된 지도를 출력하는 문제이다. 
지도의 가로,세로 크기를 입력받고 바다와 섬을 각각 o x 으로 입력받는다. 
x (섬) 주변에 o(바다)가 3개 이상 위치하면 섬은 50년뒤 사라지기때문에 x 를 o으로 변경한 뒤 최소 지도의 크기를 출력하는 문제이다.

📌코드 설계하기

지도의 크기와 지도를 모두 입력받는다.

섬 (X) 주변의 바다(o)의 개수 3개이상인지 아닌지 체크한다. (함수를 만들어서 처리하기 - dy[] ,dx[] ) 

주변에 바다의 개수가 3개 이상인 섬 (X)를 바다(o)으로 변경한다. 

모든 섬 (x)을 포함하는 가장 작은 직사각형을 출력한다.  => 이 부분 해결하는게 개인적으로 조금 어렵게 느낌. 

📌 가능한 시간복잡도

1. 입력받은 지도의 모든곳을 체크해야하고 각각 지도의 입력된 칸에서 상하좌우 4가지 방향을 모두 탐색해야하니까
시간복잡도는 O(R*C) 입니다. 

📌 정답 코드

import java.util.*;

public class Main {
    static int R, C;
    static char[][] map;
    static boolean[][] sink;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();
        sc.nextLine();

        map = new char[R][C];
        sink = new boolean[R][C];

        for (int i = 0; i < R; i++) {
            map[i] = sc.nextLine().toCharArray();
        }

        // 1. 각 땅('X')이 가라앉는지 확인
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == 'X' && shouldSink(i, j)) {
                    sink[i][j] = true;
                }
            }
        }

        // 2. 가라앉은 곳 '.'으로 변경
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (sink[i][j]) {
                    map[i][j] = '.';
                }
            }
        }

        // 3. 남은 섬들의 최소 영역 찾기
        int minX = R, maxX = 0, minY = C, maxY = 0;
        boolean found = false;

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == 'X') {
                    found = true;
                    minX = Math.min(minX, i);
                    maxX = Math.max(maxX, i);
                    minY = Math.min(minY, j);
                    maxY = Math.max(maxY, j);
                }
            }
        }

        // 4. 최소 직사각형 영역 출력
        if (found) {
            for (int i = minX; i <= maxX; i++) {
                for (int j = minY; j <= maxY; j++) {
                    System.out.print(map[i][j]);
                }
                System.out.println();
            }
        }
    }

    // 특정 좌표 (x, y)의 땅이 가라앉는지 확인하는 함수
    static boolean shouldSink(int x, int y) {
        int waterCount = 0;
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (nx < 0 || ny < 0 || nx >= R || ny >= C || map[nx][ny] == '.') {
                waterCount++;
            }
        }
        return waterCount >= 3;
    }
}