[백준/JAVA] 5212번: 지구 온난화

📖 문제

5212번: 지구 온난화

 

 

 

💡  풀이 방식

• 구현, 시뮬레이션

 

1. 원본 지도 origin과 값을 변경할 지도 map에 값을 입력받으면서, 큐에 땅(X)의 위치를 저장한다.

(원본 지도 origin 따로 저장해두는 이유 : 나중에 땅 인근이 바다인지 아닌지 판단할 때 변경된 값으로 판단하면 안 되므로)

 

2. 모든 땅의 위치를 돌며, 인접한 3면 이상이 바다로 둘러싸였다면 잠기게 만들고, 잠기지 않았다면 현재 (행,열)의 값과 땅이 위치하는 최소/최대 행/열 인덱스를 비교해 갱신한다.

 

3. 2에서 구한 (최소 행 ~ 최대 행) (최소 열 ~ 최대 열)에 위치한 모든 값을 출력한다.

 

 

💥 유의사항

땅의 인접한 4방향이 땅인지 바다인지 판별할 때, 변경된 값의 영향을 받게 해선 안 된다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};
    
    static int R,C;
    static char[][] map, origin;
    static Queue<int[]> q = new ArrayDeque<>(); // 땅 위치 저장용 큐
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        
        map = new char[R][C];
       origin = new char[R][C];
 
        for(int i = 0 ; i < R ; i++) {
            String str = br.readLine();
            for(int j = 0 ; j < C ; j++) {
                map[i][j] = str.charAt(j);
               origin[i][j] = map[i][j];
                
                if(map[i][j] == 'X')    // 큐에 땅 위치 추가
                    q.add(new int[] {i, j});
            }
        }
        
        int minR = R;
        int maxR = 0;
        int minC = C;
        int maxC = 0;
        
        while(!q.isEmpty()) {
            int cnt = 0;
            boolean survived = true;    // 땅이 50년 후 잠기는지 확인용 변수
            int[] now = q.poll();
            
            for(int d = 0 ; d < 4 ; d++) { // 4방향 탐색
                int nr = now[0] + dr[d];
                int nc = now[1] + dc[d];
                
                if(!inRange(nr, nc))    // 지도에 없는 곳, 지도 범위를 벗어난 칸은 모두 바다
                    cnt++;
                else {
                    if(origin[nr][nc] == '.') {
                        cnt++;
                    }
                }
            }
            
            if(cnt >= 3) {    // 인접한 3칸 이상에 바다가 있다면, 그 땅은 잠김
                map[now[0]][now[1]] = '.';
                survived = false;
            }
            
            if(survived) {    // 잠기지 않고 살아남은 경우, X가 위치하는 행과 열의 최소 최대 위치를 구한다.
                minR = Math.min(minR, now[0]);
                minC = Math.min(minC, now[1]);
                maxR = Math.max(maxR, now[0]);
                maxC = Math.max(maxC, now[1]);
            }
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i = minR ; i <= maxR ; i++) {
            for(int j = minC ; j <= maxC ; j++) {
                sb.append(map[i][j]);
            }
            sb.append("\n");
        }
        
        System.out.println(sb.toString());
    }
    
    private static boolean inRange(int r, int c) {
        return 0 <= r && r < R && 0 <= c && c < C;
    }
}
 

 

 

 

 

➕ 다른 풀이 방식

- 원본 배열을 저장해두지 않고, 그냥 땅에서 바다로 바뀐 애를 '.'와 'X'이 아닌 임의의 값으로 바꿔서 나중에 카운트 되지 않도록 했다!

담엔 이렇게 풀자,,

백준 5212 - 지구 온난화 (java)

 

 

- survived 변수도 필요 없고 그냥 else문으로 바로 처리 가능

[백준 Baekjoon] 5212번 지구 온난화 - JAVA

---

💦 어려웠던 점

- 50분 소요 (아이디어 12분, 푸는 데 18분, 디버깅 20분)

- 당연히 칸이 X인 칸만 큐에 추가했다고 생각했는데 그 조건문을 빠뜨렸었다!!! (정신 어데로!!)

- 땅이 있는 위치 중 가장 왼쪽-오른쪽의 열 인덱스 가져오고, 가장 위쪽-아래쪽의 행 인덱스 가져올 생각은 거북이 문제 풀면서 비슷하다 느꼈다.

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 예외 케이스 참고

글 읽기 - 어느 케이스에서 틀린건지 모르겠습니다!

2 5
...XX
....X