[BOJ] 5212 지구 온난화 C++ nov

#INFO

알고리즘 유형 : 시뮬레이션 & 구현

난이도 : SILVER2

 

#SOLVE

현재 지도의 모습을 기준으로 50년 뒤의 지도의 모양을 출력하는 구현 문제이다. 

우선 2차원 배열을 선언한 뒤 현재 지도의 모습을 배열에 저장한다. "."으로 표시된 부분은 "바다"이며, "X"로 표시된 부분은 "섬"이다.

    // #1 Input & init Value
    vector<vector<char>> board;
    int R, C;
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        vector<char> line(C);
        for (int j = 0; j < C; j++) {
            cin >> line[j];
        }
        board.push_back(line);
    }

 

문제 조건에 의하면 현재 섬을 기준으로 인접한 세 칸 혹은 네 칸이 바다(".")가 있는 땅은 50년 이후에 바다로 변한다.

예시로 아래 보라색 땅은 세 면이 바다로 둘러싸여 있기에 바다로 변하지만 빨간색 땅은 두 면이 바다로 둘러 싸여져 있기에 바다로 변하지 않는다.

 

또한 지도를 벗어나는 범위도 모두 바다로 판별하기에, 좌측 하단의 땅과 같은 케이스 또한 50년 뒤에 바다로 변한다.

 

 

50년 뒤 지도의 모습을 저장할 bool type 2차원 벡터를 선언한다. 

기존 board에 바로 정보를 업데이트하면 다음 땅의 정보를 계상할때 영향이 가기에 별도로 벡터를 선언하였다.

    // check_board : 50년 뒤 땅의 예상 모습을 저장하는 벡터
    // * 바로 board에 정보를 업데이트하면 계산에 영항이 가기에 별도의 bool 벡터를 선언한다.
    // false : 바다 , true : 섬
    vector<vector<bool>> check_board(R, vector<bool>(C, false));
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (board[i][j] == 'X') check_board[i][j] = true;
        }
    }

 

기존 board에 저장된 지도 정보를 기준으로 check_board를 업데이트한다. 

    // 인접한 바다의 영역을 기준으로 check_board를 업데이트
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[i].size(); j++) {
            int check = 0;
            if (board[i][j] == 'X') {
                if (i - 1 >= 0) {
                    if (board[i-1][j] == '.') check++;
                }
                if (i + 1 < board.size()) {
                    if (board[i+1][j] == '.') check++;
                }
                if (j - 1 >= 0) {
                    if (board[i][j-1] == '.') check++;
                }
                if (j + 1 < board[i].size()) {
                    if (board[i][j+1] == '.') check++;
                }

                // 배열의 범위를 벗어난 경우 -> 바다로 판정
                if (i -1 < 0) check++;
                if (i + 1 >= board.size()) check++;
                if (j - 1 < 0) check++;
                if (j + 1 >= board[i].size()) check++;

                if (check >= 3) {
                    check_board[i][j] = false;
                }

            }
        }
    }

 

다음으로 check_board 벡터에 저장된 정보를 기반으로 기존 Board에 50년 뒤의 지도의 모습을 업데이트한다.

    // Check_board를 기준으로 기존 board를 업데이트
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[i].size(); j++) {
            if (check_board[i][j] == false) board[i][j] = '.';
            else board[i][j] = 'X';
        }
    }

 

마지막으로 업데이트된 board 배열을 모든 섬을 포함하는 가장 작은 직사각형이 되도록 잘라 주어야 한다. 

아이디어는 간단하다. board에 저장된 모든 정보를 루프를 돌며 가장 큰 column, row 값과 가장 작은 column, row 값을 저장한 뒤 해당하는 범위에 있는 정보만을 출력하도록 하였다. 

    // 지도를 자를 범위를 설정
    int min_column = 99, max_column = -1, min_row = 99, max_row = -1;
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[i].size(); j++) {
            if (board[i][j] == 'X') {
                if (min_column > i) min_column = i;
                if (max_column < i) max_column = i;
                if (min_row > j) min_row = j;
                if (max_row < j) max_row = j;
            }
        }
    }

    // Output
    for (int i = min_column; i <= max_column; i++) {
        for (int j = min_row; j <= max_row; j++) {
            cout << board[i][j];
        }
        cout << endl;
    }

 

#CODE

C++

/////////////////////////////////////////////////////////////////////
/** Info
 * developer : nov
 * BOJ 5212 지구온난화
 * 제출일자 : 2024.11.24(일)
 * ver : 1.0
**/
/////////////////////////////////////////////////////////////////////

#include <iostream>
#include <vector>
using namespace std;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    // #1 Input & init Value
    vector<vector<char>> board;
    int R, C;
    cin >> R >> C;
    for (int i = 0; i < R; i++) {
        vector<char> line(C);
        for (int j = 0; j < C; j++) {
            cin >> line[j];
        }
        board.push_back(line);
    }

    // check_board : 50년 뒤 땅의 예상 모습을 저장하는 벡터
    // * 바로 board에 정보를 업데이트하면 계산에 영항이 가기에 별도의 bool 벡터를 선언한다.
    // false : 바다 , true : 섬
    vector<vector<bool>> check_board(R, vector<bool>(C, false));
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (board[i][j] == 'X') check_board[i][j] = true;
        }
    }

    // 인접한 바다의 영역을 기준으로 check_board를 업데이트
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[i].size(); j++) {
            int check = 0;
            if (board[i][j] == 'X') {
                if (i - 1 >= 0) {
                    if (board[i-1][j] == '.') check++;
                }
                if (i + 1 < board.size()) {
                    if (board[i+1][j] == '.') check++;
                }
                if (j - 1 >= 0) {
                    if (board[i][j-1] == '.') check++;
                }
                if (j + 1 < board[i].size()) {
                    if (board[i][j+1] == '.') check++;
                }

                // 배열의 범위를 벗어난 경우 -> 바다로 판정
                if (i -1 < 0) check++;
                if (i + 1 >= board.size()) check++;
                if (j - 1 < 0) check++;
                if (j + 1 >= board[i].size()) check++;

                if (check >= 3) {
                    check_board[i][j] = false;
                }

            }
        }
    }

    // Check_board를 기준으로 기존 board를 업데이트
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[i].size(); j++) {
            if (check_board[i][j] == false) board[i][j] = '.';
            else board[i][j] = 'X';
        }
    }


    // 지도를 자를 범위를 설정
    int min_column = 99, max_column = -1, min_row = 99, max_row = -1;
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[i].size(); j++) {
            if (board[i][j] == 'X') {
                if (min_column > i) min_column = i;
                if (max_column < i) max_column = i;
                if (min_row > j) min_row = j;
                if (max_row < j) max_row = j;
            }
        }
    }

    // Output
    for (int i = min_column; i <= max_column; i++) {
        for (int j = min_row; j <= max_row; j++) {
            cout << board[i][j];
        }
        cout << endl;
    }


    return 0;
}