[ baekjoon ] #5212 지구 온난화

백준 #5212 지구 온난화

문제 요약

---

• 지구 온난화로 인해 해수면이 상승해 섬의 일부가 바다에 잠겼다.
• 지구 온난화가 계속 될 경우 남해의 지도가 어떻게 바뀔지 궁금해졌다.
• R*C 크기의 다도해 지도('X'는 땅, '.'은 바다)
• 50년 후 인접한 세 칸 또는 네 칸에 바다가 있는 땅은 모두 잠긴다.
• 50년 후에도 섬은 적어도 한 개 있다.
• 모든 섬을 포함하는 가장 작은 직사각형 구하기 !

💡 Idea(BFS)

1. 어떤 경우에 땅이 잠길까 ?
   • 섬에서 상, 하, 좌, 우를 확인한 후 바다가 3개 이상일 경우
     → 지도를 벗어난 곳도 바다로 처리해줘야한다 !
2. 땅이 잠기는 경우 어떻게 처리할 것인가 ?
   • 땅이 잠기는 경우에는 'X'에서 '.'로 바꿔준다.
     → 이때 다음 섬의 주변을 확인할 때 문제가 발생한다.
     → 섬에서 땅으로 바뀐 경우 visit 배열의 값을 1로 바꿔준다 !
3. 가장 작은 직사각형을 어떻게 구하지 ?
   • 지도를 돌면서 제일 처음으로 나온 섬의 위치와 마지막 위치를 저장하자.
     → 이 경우, 출력할 때도 이중 for 써야하므로 비효율적이라고 판단.
   • 섬의 주변을 확인할 때 잠기지 않은 경우에 한해 start, end 좌표를 저장하자 !
     ① 처음 섬의 위치를 start, end에 저장
     ② 처음이 아닌 경우 비교하여 저장
     → start의 y좌표보다 작은 경우 start의 y값 갱신
     → end의 x좌표보다 큰 경우 end의 x값 갱신
     → end의 y좌표보다 큰 경우 end의 y값 갱신
     ∵ start의 좌표는 x, y 둘 다 작아야하고 end의 좌표는 x, y 둘 다 커야하기 때문

[ SourceCode ]

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int visit[10][10];

int main() {
    int R, C;
    cin >> R >> C;
    vector <vector<char>> map(R, vector<char>(C)); // 다도해 지도 (R * C)
    queue <pair<int, int>> island;

    for(int i=0; i<R; i++) {
        for(int j=0; j<C; j++) {
            cin >> map[i][j];
            if(map[i][j] == 'X') { // 섬일 경우 push !
                island.push({i, j});
            }
        }
    }

    int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상, 하, 좌, 우
    pair <int, int> start, end;
    bool check = false;

    while(!island.empty()) {
        pair<int, int> now = island.front();
        island.pop();

        int cnt = 0;
        for(int i=0; i<4; i++) {
            int nx = now.first + dir[i][0];
            int ny = now.second + dir[i][1];

            if(nx < 0 || nx >= R || ny < 0 || ny >= C) {
                cnt++;
                continue;
            }

            if(map[nx][ny] == '.' && !visit[nx][ny]) {
                cnt++;
            }
        }

        if(cnt >= 3) { // 섬이 잠긴 경우
            map[now.first][now.second] = '.';
            visit[now.first][now.second] = 1;
        }
        else {
            if(!check) { // 처음일 경우 start, end 대입
                check = true;
                start = now;
                end = now;
            }

            else {
                if(start.second > now.second) {
                    start.second = now.second;
                }
                if(end.first < now.first) {
                    end.first = now.first;
                }
                if(end.second < now.second) {
                    end.second = now.second;
                }
            }
        }
    }

    if(start == end) {
        cout << 'X';
    }

    else {
        for(int i=start.first; i<=end.first; i++) {
            for(int j=start.second; j<=end.second; j++) {
                cout << map[i][j];
            }
            cout << endl;
        }
    }

    return 0;
}

Feedback

---

1. 처음에 잠기는 섬('X')을 바다('.')로 바꾸기만 함.
   → 원래 바다였는지, 잠겨서 바다가 된 건지 판단 불가능
   → 이렇게 값을 바꾸게 될 경우 어떤 문제가 발생하는지 생각해보기 !!!