BOJ_5212 / 지구 온난화

📌 문제 탐색하기

• 입력:
  • 첫 줄에 지도의 크기 R과 C가 주어짐. (1 ≤ R, C ≤ 10)
  • 다음 R개의 줄에 현재 지도가 주어지고, X는 땅을 .는 바다를 나타낸다.
• 출력:
  • 50년 후의 지도를 출력한다.
  • 50년 후 모든 땅(X)을 포함하는 가장 작은 직사각형 영역만 출력해야 한다.

---

📌 어떤 알고리즘?

• 시뮬레이션 및 구현:
  • 50년 후, 인접한 세 칸 또는 네 칸에 바다가 있는 땅은 모두 잠긴다.
  • 모든 땅의 좌표를 순회하면서 잠겨야 할 땅을 찾아 리스트에 저장한다.
  • 이후 모든 땅을 포함하는 가장 작은 직사각형을 찾아 해당 범위만 출력한다.
• 경계 설정을 위한 패딩 추가:
  • 범위 검사를 쉽게 하기 위해 지도 주변에 패딩을 추가하여 모든 경계를 .로 초기화함. 이를 통해 경계 검사 시 배열 인덱스 오류를 방지할 수 있다.

---

📌 코드 설계하기

1. 입력 처리:
   • 지도 크기 R, C와 지도를 입력받고, 지도 배열 grid를 만들고 경계에 . 패딩을 추가하여 초기화한다.
2. 침수될 땅 탐색:
   • 지도 전체를 순회하며 땅(X)인 위치에 대해 인접한 4칸을 확인함.
   • 인접한 4칸 중 바다(.)가 3개 이상인 경우 해당 위치는 침수될 땅으로 간주하고, 리스트 find에 추가한다.
3. 침수 적용:
   • find 리스트에 포함된 좌표를 순회하며, 침수될 위치를 바다(.)로 변경한다.
4. 출력 범위 설정:
   • 지도에서 침수 후 남아 있는 땅(X)의 최소 및 최대 행과 열을 찾아 minX, maxX, minY, maxY로 설정한다.
   • 이 범위에 맞춰 50년 후 지도의 축소된 직사각형 영역만 출력한다.

---

📌 정답 코드

java
코드 복사
package BOJ_5212;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_5212 {
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static String[][] grid;
    static int[] dx = {0, 0, 1, -1}; // 동, 서, 남, 북 방향 설정
    static int[] dy = {1, -1, 0, 0}; // 동, 서, 남, 북 방향 설정
    static List<int[]> find = new ArrayList<>(); // 침수될 땅을 저장할 리스트

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(bf.readLine(), " ");
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        grid = new String[R + 2][C + 2];

        // 경계에 바다 패딩 추가
        for (int i = 0; i <= C + 1; i++) {
            grid[0][i] = ".";
            grid[R + 1][i] = ".";
        }
        for (int i = 1; i <= R; i++) {
            grid[i][0] = ".";
            grid[i][C + 1] = ".";
        }

        // 입력 그리드 설정
        for (int i = 1; i <= R; i++) {
            String[] strings = bf.readLine().split("");
            for (int j = 1; j <= C; j++) {
                grid[i][j] = strings[j - 1];
            }
        }

        // 침수될 위치 탐색
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                int count = 0;
                if (grid[i][j].equals("X")) {
                    for (int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        if (nx >= 0 && nx <= R + 1 && ny >= 0 && ny <= C + 1 && grid[nx][ny].equals(".")) {
                            count++;
                        }
                    }
                    if (count >= 3) { // 인접한 바다가 3개 이상이면 침수될 땅으로 추가
                        find.add(new int[]{i, j});
                    }
                }
            }
        }

        // 침수될 위치를 바다로 변경
        for (int[] pos : find) {
            grid[pos[0]][pos[1]] = ".";
        }

        // 최소 직사각형 범위 찾기
        int minX = R, maxX = 1, minY = C, maxY = 1;
        for (int i = 1; i <= R; i++) {
            for (int j = 1; j <= C; j++) {
                if (grid[i][j].equals("X")) {
                    minX = Math.min(minX, i);
                    maxX = Math.max(maxX, i);
                    minY = Math.min(minY, j);
                    maxY = Math.max(maxY, j);
                }
            }
        }

        // 최종 결과 출력 (최소 직사각형 범위만 출력)
        for (int i = minX; i <= maxX; i++) {
            for (int j = minY; j <= maxY; j++) {
                System.out.print(grid[i][j]);
            }
            System.out.println();
        }
    }
}

---

📌 시간 복잡도?

• 시간 복잡도:
  • R x C 크기의 지도에서 모든 칸을 확인해야 하므로 시간 복잡도는 O(R * C)임.
  • R과 C가 최대 10이므로 O(100)으로 충분히 빠르게 동작할 수 있음.
• 공간 복잡도:
  • 지도 크기에 따라 R C만큼의 grid 배열과 find 리스트가 필요하므로 공간 복잡도는 O(R C)이다.