[BOJ] 5212: 지구 온난화 (JAVA)

문제

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

 

여담

두 번째 예제가 틀리게 나와서 문제를 다시 읽어보니 "지도에 없는 곳, 지도의 범위를 벗어나는 칸은 모두 바다이다"라는 문장이 있었다. 이를 사용한 예제가 있어서 다행이지 아니었으면 놓칠 뻔했다..! 왜 자꾸 끝을 안 읽냐 끝이 중요하다고..

 

풀이

50년이 지나면 인접한 세 칸 또는 네 칸에 바다가 있는 땅은 모두 잠긴다고 한다. 즉, BFS 탐색을 통해 땅 주변에 위치한 바다의 수를 센 후 조건에 따라 지도를 변경해야 한다.

 

따라서 다음과 같은 과정을 수행하면 된다.

1. 땅의 위치를 큐에 저장한다.
2. 큐에서 땅의 위치를 poll() 한다.
3. 인접한 칸(=상하좌우)에 위치한 바다의 수를 구한다.
   • 이때, 지도를 벗어나는 칸도 모두 바다이다.
     • 바다인 경우: nx < 0 || ny < 0 || nx >= R || ny >= C || map[nx][ny] == '.'
4. 땅 주변에 바다인 칸이 3개 이상이라면, 땅은 물에 잠긴다.
   • newMap[x][y] = '.'
5. 땅 주변에 바다가 3개 미만이라면, 지도의 크기 조정을 위해 x와 y의 최댓값/최솟값을 구한다.
   • minX = Math.min(minX, x)
   • minY = Math.min(minY, y)
   • maxX = Math.max(maxX, x)
   • maxY = Math.max(maxY, y)
6. 큐가 빌 때까지 2번 ~ 5번 과정을 반복한다.

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static int R, C;
    static int minX, minY, maxX = -1, maxY = -1;
    static char[][] map, newMap;
    static Queue<int[]> queue = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // X: 땅, .: 바다
        // 인접한 세 칸, 또는 네 칸에 바다가 있는 칸은 모두 잠김
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        newMap = new char[R][C];
        minX = R; minY = C;
        for (int i = 0; i < R; i++) {
            String line = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = line.charAt(j);
                if (map[i][j] == 'X') { // 땅의 위치 큐에 저장
                    queue.offer(new int[]{i, j});
                }
            }
        }

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                newMap[i][j] = map[i][j];
            }
        }
        bfs();

        StringBuilder sb = new StringBuilder();
        for (int i = minX; i <= maxX; i++) {
            for (int j = minY; j <= maxY; j++) {
                sb.append(newMap[i][j]);
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }

    public static void bfs() {
        int[][] move = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            int x = now[0], y = now[1];

            // 네 방향 탐색하기
            int sea = 0;
            for (int i = 0; i < 4; i++) {
                int nx = x + move[i][0];
                int ny = y + move[i][1];

                // 지도를 벗어나는 칸은 모두 바다 & 배열의 값이 '.'이면 바다
                if (nx < 0 || ny < 0 || nx >= R || ny >= C || map[nx][ny] == '.') {
                    sea++;
                }
            }

            if (sea >= 3) { // 주변에 바다가 3개 이상이면 물에 잠김
                newMap[x][y] = '.';
            } else { // 지도 크기 조절을 위해 최소/최대 x, y 구하기
                minX = Math.min(minX, x);
                minY = Math.min(minY, y);
                maxX = Math.max(maxX, x);
                maxY = Math.max(maxY, y);
            }
        }
    }
}

---