백준 5212번 지구 온난화

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class GlobalWarming {
    static int R,C;
    static char[][]map;
    static int[] dr = {1,0,-1,0};
    static int[] dc = {0,1,0,-1};
    static List<int[]> list = new ArrayList<>();
    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];
        int xcnt = 0;
        for (int i = 0; i < R; i++) {
            String str = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = str.charAt(j);
                if(map[i][j]=='X') xcnt++;
            }
        }

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                bfs(i,j);
            }
        }
        if(list.size()!= xcnt){
            for (int i = 0; i < list.size(); i++) {
                int[] change = list.get(i);
                map[change[0]][change[1]] = '.';
            }
        }


        StringBuilder sb = new StringBuilder();
        boolean flag;
        ArrayDeque<Integer> rowQue = new ArrayDeque<>();
        for (int i = 0; i < R; i++) {
            flag = false;
            for (int j = 0; j < C; j++) {
                if(map[i][j] == 'X'){
                    flag = true;
                    break;
                }
            }
            if(flag){
                rowQue.add(i);
            }
        }
        ArrayDeque<Integer> colQue = new ArrayDeque<>();
        for (int i = 0; i < C; i++) {
            flag = false;
            for (int j = 0; j < R; j++) {
                if(map[j][i] == 'X'){
                    flag = true;
                    break;
                }
            }
            if(flag){
                colQue.add(i);
            }
        }
        int rowstart = 0;
        int rowend = R-1;
        int colstart = 0;
        int colend = C-1;
        if(!rowQue.isEmpty()){
            rowstart = rowQue.peekFirst();
            rowend = rowQue.peekLast();
        }

        if(!colQue.isEmpty()){
            colstart = colQue.peekFirst();
            colend = colQue.peekLast();
        }

        for (int i = rowstart; i <= rowend; i++) {
            for (int j = colstart; j <= colend; j++) {
                sb.append(map[i][j]);
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
    public static void bfs(int row, int col){
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[] { row, col});
        while (!que.isEmpty()){
            int[] current = que.poll();
            int crow = current[0];
            int ccol = current[1];
            int count = 0;
            if(map[crow][ccol]=='X'){
                for (int i = 0; i < 4; i++) {
                    int nrow = crow + dr[i];
                    int ncol = ccol + dc[i];
                    if((nrow<0||ncol<0||nrow>=R||ncol>=C)||(map[nrow][ncol]=='.')){
                        count++;
                    }
                }
            }
            if(count>=3){
                list.add(new int[]{crow,ccol});
            }
        }
    }
}

풀이방법

이 문제는 X를 조건에 따라 지우고 조건에 따라 출력하는 문제이다.
조건에 따라 지우는건 어렵지 않다.
다만 출력시 1. X가 적어도 하나는 존재한다. 2.섬의 크기에 맞춰서 지도를 축소해서 출력해야 하는 점이 복잡하다.

1. 입력을 받고, bfs()함수를 통해 사방을 확인해서 지워야할 좌표를 list에 담아준다.
2. X가 적어도 하나는 존재해야하므로, 입력받은 X의 개수와 지워지는 X의 개수가 다를때만 (전부 다 지워지는경우 제외) list의 좌표에 해당하는 X를 .으로 지워준다.
3. 행을 하나씩 확인해서 X가 나오는 행이 있다면 그때의 행의 인덱스를 rowQue(deque)에 담아준다.
4. 열을 하나씩 확인해서 X가 나오는 열이 있다면 그때의 열의 인덱스를
   colQue(deque)에 담아준다.
5. rowQue의 맨앞,뒤가 각각 rowstart, rowend가 되고,colQue의 맨 앞,뒤가 colstart,colend가 된다.
6. 이를 바탕으로 시작점과 끝점을 통해 stringBuilder로 만들어서 출력해준다.

후기

크게 어렵지 않은 문제인줄 알았는데, 출력조건을 맞추는것이 쉽지 않았다.