(C++) - 백준(BOJ) 5212번 : 지구온난화

www.acmicpc.net/problem/5212

5212번: 지구 온난화

시뮬레이션 문제였습니다.

 

풀이방법

 1. 지도를 입력받습니다.

 2. 바다로 될 경우는 'X'의 상하좌우(인접한 곳)이 바다이고 3칸 이상일 때입니다. 비교할 상하좌우 칸이 지도를 넘어가는 경우에도 바다이므로 세줍니다. 세준 이후에는 바다로 될 지형을 ' '으로 바꿔줍니다. 

 3. 'X'인 곳을 정답 배열 ans에 옮겨줍니다.

 4. ans의 'X'가 등장하는 최소 최대의 행,열을 구해준 뒤 해당 영역만큼 출력합니다.

 

Code

#include <iostream>
#include <algorithm>
using namespace std;
using pii = pair<int,int>;
char map[11][11];
char ans[11][11];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int r,c;

int getLastYidx(){
    int idx = 0;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(ans[i][j] == 'X') idx = max(idx,i);
        }
    }
    return idx;
}

pii getLastXidx(){
    int idxX = 0;
    int idxY = 0;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(ans[i][j] == 'X') idxX = max(idxX,i), idxY = max(idxY,j);
        }
    }
    return {idxX,idxY};
}

pii getFirstXidx(){
    int idxX = 1000;
    int idxY = 1000;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(ans[i][j] == 'X') idxX = min(idxX,i), idxY = min(idxY,j);
        }
    }
    return {idxX,idxY};
}

int main(){
    cin >> r >> c;
    for(int i = 0; i < r; i++)
            cin >> map[i];

    for(int i = 0; i < r; i++){
        for(int j = 0 ; j < c; j++){
            if(map[i][j] != 'X') continue;
            int cnt = 0;
            for(int k = 0; k < 4; k++){
                int x = i + dx[k];
                int y = j + dy[k];
                if(x < 0 || x >= r || y < 0 || y >= c) {cnt++; continue;}
                if(map[x][y] == '.') cnt++;
            }
            if(cnt >= 3) map[i][j] = ' ';
        }
    }
    
    for(int i = 0; i < r; i++) {
        for(int j = 0; j < c; j++){
            if(map[i][j] == 'X') ans[i][j] = map[i][j];
        }
    }

    pii firstIdx = getFirstXidx();
    pii lastIdx = getLastXidx();

    for(int i = firstIdx.first; i <= lastIdx.first; i++) {
        for(int j = firstIdx.second; j <= lastIdx.second; j++){
            if(ans[i][j] != 'X') cout << '.';
            else cout << ans[i][j];
        }
        cout << '\n';
    }
}

 

Test Case

 몇 가지 반례를 직접 작성해 보았습니다. 

 

input

4 4
X...
X...
X...
X...

답

X

X

 

input

4 4
XX.X
.X..
...X
X...

답

X

 

input

3 5
XXX..
.....
..XXX

답

X..
...
..X