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

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

5212번: 지구 온난화

 

풀이

언뜻 보면 BFS / DFS 문제 같지만 섬인 부분만 체크하면 되는 조금 생각해야하는 구현 문제다.

 

그래프 탐색 유형처럼 접근하긴 했는데 map 에서 X 인 부분의 상하좌우를 확인했다.

X 의 상하좌우가 map 의 밖에 있거나 바다일 경우 cnt 를 하나씩 늘려주었고

cnt >= 3 일때 X 를 임시로 a 로 바꿔주었다.

 

지도를 줄이는 부분에서 조금 생각해야할 부분이 있었는데 

다시 map 을 탐색하면서 X 인 부분이 있을 때마다 최소 x, y 좌표와 최대 x, y 좌표를 갱신했다.

그리고 임시로 바꿔준 a 는 ' . ' 으로 다시 바꿔주었고 

최소 x, y 좌표와 최대 x, y 좌표를 기준으로 map 을 출력했다.

 

전체 코드

#include <iostream>
#include <algorithm>

using namespace std;

int R, C;
char map[13][13];
int goY[4] = { 0,0,1,-1 }, goX[4] = { 1,-1,0,0 };
int minY = 987654321, minX = 987654321;
int maxY = 0, maxX = 0;

bool is_in_board(int y, int x) {
    if (y < 0 || x < 0 || y >= R || x >= C) return false;
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> R >> C;

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

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (map[i][j] == 'X') {
                int cnt = 0;
                for (int k = 0; k < 4; k++) {
                    int nextY = i + goY[k], nextX = j + goX[k];
                    if (!is_in_board(nextY, nextX)) {
                        cnt++;
                        continue;
                    }
                    if (map[nextY][nextX] == '.') cnt++;
                }
                if (cnt >= 3) map[i][j] = 'a';
            }
        }
    }

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (map[i][j] == 'a') map[i][j] = '.';
            if (map[i][j] == 'X') {
                if (i <= minY) minY = i;
                if (j <= minX) minX = j;
                if (i >= maxY) maxY = i;
                if (j >= maxX) maxX = j;
            }
        }
    }

    for (int i = minY; i <= maxY; i++) {
        for (int j = minX; j <= maxX; j++) cout << map[i][j];
        cout << '\n';
    }
}