문제 설명

N x N 픽셀의 해역 사진이 주어집니다. '.'은 해양, '#'은 육지를 나타내며, 상하좌우로 연결된 육지 픽셀은 하나의 섬을 이룹니다. 해수면 상승으로 인해 해양과 인접한 육지 픽셀이 침수될 때, 완전히 사라지는 섬의 개수를 계산하세요.

입력 형식

첫 줄에 정수 N(1 ≤ N ≤ 1000)이 주어집니다. 다음 N줄에는 N개의 문자로 구성된 문자열이 입력되며, 사진의 테두리는 항상 해양('.')입니다.

출력 형식

완전히 침수되는 섬의 개수를 출력합니다.

예제 입력 1

7
.......
.##....
.##....
....##.
..####.
...###.
.......

예제 출력 1

1

예제 입력 2

9
.........
.##.##...
.#####...
.##.##...
.........
.##.#....
.#.###...
.#..#....
.........

예제 출력 2

1

해결 전략

BFS를 이용해 각 섬을 탐색하며 다음을 계산합니다:

• 전체 육지 수: 섬 내 모든 '#' 픽셀
• 침수 육지 수: 상하좌우 중 하나라도 해양('.')과 인접한 픽셀

전체 육지 수와 침수 육지 수가 동일하면 해당 섬은 완전히 침수됩니다.

C++ 구현

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

typedef pair<int, int> Coord;
const int GRID_SIZE = 1005;
char map[GRID_SIZE][GRID_SIZE];
bool visited[GRID_SIZE][GRID_SIZE];
int mapSize;
int rowDir[4] = {-1, 0, 1, 0};
int colDir[4] = {0, 1, 0, -1};

void floodFill(int startRow, int startCol, int &landTotal, int &coastCount) {
    queue<Coord> coordQueue;
    coordQueue.push({startRow, startCol});
    visited[startRow][startCol] = true;

    while (!coordQueue.empty()) {
        Coord current = coordQueue.front();
        coordQueue.pop();
        landTotal++;
        bool adjacentOcean = false;

        for (int i = 0; i < 4; i++) {
            int nextRow = current.first + rowDir[i];
            int nextCol = current.second + colDir[i];

            if (nextRow < 0 || nextRow >= mapSize || nextCol < 0 || nextCol >= mapSize) 
                continue;
            if (map[nextRow][nextCol] == '.') {
                adjacentOcean = true;
                continue;
            }
            if (visited[nextRow][nextCol]) 
                continue;

            visited[nextRow][nextCol] = true;
            coordQueue.push({nextRow, nextCol});
        }
        if (adjacentOcean) 
            coastCount++;
    }
}

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

    int submergedIslands = 0;
    for (int i = 0; i < mapSize; i++) {
        for (int j = 0; j < mapSize; j++) {
            if (map[i][j] == '#' && !visited[i][j]) {
                int landTotal = 0, coastCount = 0;
                floodFill(i, j, landTotal, coastCount);
                if (landTotal == coastCount) 
                    submergedIslands++;
            }
        }
    }
    cout << submergedIslands;
    return 0;
}