[백준] 5212 - 지구 온난화 (C++)

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

 다도해의 지도는 R × C 크기의 그리드로 나타나고, 지도의 X는 땅을, .은 바다를 나타낸다. 50년 뒤에 인접한 세 칸 또는 네 칸에 바다가 있는 땅은 모두 잠겨버리고, 이로 인해 지도의 크기도 줄어든다. 지도의 크기는 모든 섬을 포함하는 가장 작은 직사각형이며, 50년이 지난 후에도 섬은 적어도 1개가 존재한다. 지도에 없는 곳 또는 지도의 범위를 벗어나는 칸은 모두 바다이다. 이때 50년 뒤의 지도를 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ R, C ≤ 10

 

지도에 없는 곳 또는 지도의 범위를 벗어나는 칸은 모두 바다로 치기 때문에 지도 배열을 R과 C보다 2씩 크게 잡아야 한다. 또, 인접한 바다가 3면 이상인지 확인할 배열과 가라앉지 않는 땅의 최소 및 최대 범위를 기록할 배열도 선언해야 한다. 확인용 함수를 하나 만들어 앞에 말한 두 배열을 갱신하면서 진행해야 한다.

 

지도 정보를 입력받을 때 string으로 받아 한 개씩 떼어내 지도 배열에 저장해야 한다는 걸 기억해야 한다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. R, C, 지도 입력받기
2. 지도의 크기만큼 이중 반복문을 돌려 인접한 세 칸 또는 네 칸에 바다가 있는지 확인
   
   1. 지도의 크기를 줄이기 위해, 땅이면서 가라앉지 않는 부분의 최소 범위와 최대 범위를 기록
3. 가라않지 않는 부분의 최소 범위와 최대 범위에 따라 반목문을 돌면서 가라앉는다면 X를, 아니라면 .을 출력

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

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

int r,c,board[12][12],edge[2][2]={{12,12},{-1,-1}},dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
bool sea[12][12];
string str;

void check(int a, int b) {
    int cnt=0;
    for (int i=0; i<4; i++) {
        if (board[a+dx[i]][b+dy[i]]==0) cnt++;
    }
    
    if (cnt<=2) {
        sea[a][b] = false;
        if (board[a][b]==1) {
            edge[0][0] = min(a,edge[0][0]);
            edge[0][1] = min(b,edge[0][1]);
            edge[1][0] = max(a,edge[1][0]);
            edge[1][1] = max(b,edge[1][1]);
        }
    }
    else sea[a][b] = true;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(); cout.tie();

    cin >> r >> c;
    for (int i=1; i<=r; i++) {
        cin >> str;
        for (int j=1; j<=c; j++) board[i][j] = (str[j-1]=='X' ? 1 : 0);
    }

    for (int i=1; i<=r; i++) {
        for (int j=1; j<=c; j++) {
            check(i,j);
        }
    }

    for (int i=edge[0][0]; i<=edge[1][0]; i++) {
        for (int j=edge[0][1]; j<=edge[1][1]; j++) {
            cout << (!sea[i][j] && board[i][j]==1 ? 'X' : '.');
        }
        cout << '\n';
    }

}