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

🌵 문제 분석

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

X와 인접한 곳에 .가 3개 이상 있으면 X가 .로 바뀐다.

X과 .으로 이루어진 RxC지도가 주어질 때 바뀐 지도를 출력하라.

(단 모든 X가 포함된 가장 작은 직사각형만 출력하기)

입력:

R C

X, .로 구성된 지도

🌵 구현 아이디어

💡 모든 X에 대하여 인접한 곳의 .개수 구하기

R, C가 최대 10이라서 모든 X에 대해 인접한 곳에 .가 몇 개 있는지 확인해도 1초 안에 탐색 가능하다.

✅  탐색 방법

5 3
...
.X.
.X.
.X.
...

1. 예제 입력 1의 경우 5*3 격자를 (0, 0)부터 (4, 2)까지 차례로 탐색
2. X를 만나면 상하좌우 인접한 곳에 .가 몇 개 있는지 확인
   1. (1, 1)에서 X를 발견했으므로 상하좌우를 확인하여 .의 개수 세기
      -> 개수가 3개 이상이므로 X를 .로 바꾼다.
   2. (2, 1)에서 X를 발견했으므로 상하좌우를 확인하여 .의 개수 세기
      -> 개수가 3개 미만이므로 그대로 둔다.
   3. (3, 1)에서 X를 발견했으므로 상하좌우를 확인하여 .의 개수 세기
      -> 개수가 3개 이상이므로 X를 .로 바꾼다.
3. 모든 X가 포함된 작은 직사각형만 출력하기
   1. 탐색이 끝났다면 지도가 아래처럼 바뀌었을 것이다.
   2. 바뀐 지도를 탐색하며 X를 만날 때마다 행, 열의 최소값과 최대값을 갱신한다.
   3. (행의 최소값~행의 최대값)*(열의 최소값~열의 최대값)에 해당하는 부분만 출력한다.

...
...
.X.
...
...

🌵 시간 복잡도

격자를 탐색하는 시간복잡도 : O(R*C)

인접한 좌표를 탐색하는 시간복잡도 : 상하좌우를 탐색하므로 O(4)

출력할 범위를 측정하기 위해 탐색하는 시간복잡도 : O(R*C)

 

따라서 전체 시간 복잡도는 O(R*C)+O(4)+O(R*C)=100+4+100=204

이므로 1초 안에 연산 가능하다.

🌵 알고리즘

구현

🌵 코드 설계

1. 입력받기
   1. int 변수에 R, C 저장
   2. char[] 배열 board에 X, . 저장
2. 탐색을 위한 방향 배열 정의
   1. dx = {0, 1, 0, -1}
   2. dy = {1, 0, -1, 0}
3. X를 찾으면 인접 좌표(상하좌우) 탐색하여 .로 바꾸기
   1. (0, 0)~(R-1, C-1)에 대하여
   2. X를 찾으면 상하좌우 탐색하며 .개수 세기
   3. 개수가 3개 이상이면 .로 바꾸기
   4. 개수가 3개 미만이면 그대로 두기
4. 출력할 지도 범위 구하기
   1. minX, minY 초기값을 Integer.MAX_VALUE로 설정
   2. maxX, maxY 초기값을 0으로 설정 
   3. (0, 0)~(R-1, C-1)에 대하여
   4. X를 찾으면 네 개의 값을 업데이트
5. 출력하기
   1. minX~maxX, minY~maxY 범위를 출력

🌵 정답 코드

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

public class Main {
    static int R, C;
    static char[][] board1, board2;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};

    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());

		//현재 지도, 50년 후 지도
        board1 = new char[R][C]; 
        board2 = new char[R][C];
        
        //입력받기
        for(int i=0; i<R; i++){
            String str = br.readLine();
            for(int j=0; j<C; j++){
                board1[i][j] = board2[i][j] = str.charAt(j);
            }
        }
		
        //X의 인접 좌표를 탐색
        for(int i=0; i<R; i++){
            for(int j=0; j<C; j++){
                if(board1[i][j]=='X'){
                	//.가 3개 이상이면 X를 .로 
                    if(find(i, j)>=3){
                        board2[i][j] = '.';
                    }
                }
            }
        }
		
        //출력할 범위를 초기화
        int minX = Integer.MAX_VALUE;
        int minY = Integer.MAX_VALUE;
        int maxX = 0;
        int maxY = 0;
		
        //출력할 범위 찾기
        for(int i=0; i<R; i++){
            for(int j=0; j<C; j++){
                if(board2[i][j]=='X'){
                    minX = Math.min(minX, i);
                    minY = Math.min(minY, j);
                    maxX = Math.max(maxX, i);
                    maxY = Math.max(maxY, j);
                }
            }
        }
        
        //범위 만큼 출력
        StringBuilder sb = new StringBuilder();
        for(int i=minX; i<=maxX; i++){
            for(int j=minY; j<=maxY; j++){
                sb.append(board2[i][j]);
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
    
    static int find(int x, int y){
        int ret = 0;
        
        //상하좌우
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            //문제에서 지도 밖의 범위도 바다라고 가정함
            if(nx<0 || nx>=R || ny<0 || ny>=C) {
                ret++;
                continue;
            }
            //바다를 찾음
            if(board1[nx][ny]=='.')
                ret++;
        }
        return ret;
    }
}