[Algorithm] Baekjoon 1109번 : 섬

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

1109번: 섬

struct Node
{
    int y;
    int x;
};
 
int dir[8][2] = { {-1,0}, {1,0}, {0,-1}, {0,1}, {-1,-1}, {-1,1}, {1,1}, {1,-1} };
int r, c;
char input[51][51];
int arr[51][51] = { 0 };
bool visited[51][51] = { false };
bool isOutermostIslands[2500] = { false };
vector<vector<int>> graph(2500);
vector<int> dp(2500, -1);
int answers[2500] = { 0 };
 
bool IsEdge(int y, int x)
{
    if (y == 0 || y == r - 1) // 맨 위 or 맨 아래
    {
        return true;
    }
    else if (x == 0 || x == c - 1)
    {
        return true;
    }
 
    return false;
}
 
void Update(int startY, int startX, int mark) // 섬은 8방향
{
    queue<Node> q;
    q.push({ startY,startX });
    arr[startY][startX] = mark;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        for (int i = 0; i < 8; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= r) continue;
            if (nextX < 0 || nextX >= c) continue;
            if (arr[nextY][nextX] != -1) continue; // 이미 다른섬이면
 
            arr[nextY][nextX] = mark;
            q.push({ nextY,nextX });
        }
    }
}
 
void FindOutermostIslands(int startY, int startX) // 바다는 상,하,좌,우로만
{
    visited[startY][startX] = true;
 
    queue<Node> q;
    q.push({ startY,startX });
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= r) continue;
            if (nextX < 0 || nextX >= c) continue;
            if (visited[nextY][nextX]) continue;
 
            if (arr[nextY][nextX] >= 1 && !isOutermostIslands[arr[nextY][nextX]]) // 방문한적 없던 섬이면
            {
                isOutermostIslands[arr[nextY][nextX]] = true;
            }
            else if (arr[nextY][nextX] == 0)
            {
                visited[nextY][nextX] = true;
                q.push({ nextY,nextX });
            }
        }
    }
}
 
void ConnectIslandsInheritance(int startY, int startX)
{
    visited[startY][startX] = true;
 
    queue<Node> q;
    q.push({ startY,startX });
 
    int curParent = 2600;
    bool tempVistiedIslands[2500] = { false };
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x;
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= r) continue;
            if (nextX < 0 || nextX >= c) continue;
            if (visited[nextY][nextX]) continue;
 
            if (arr[nextY][nextX] >= 1 && !tempVistiedIslands[arr[nextY][nextX]]) // 섬이면서 현재 BFS탐색에서 안만나본 섬
            {
                if (isOutermostIslands[arr[nextY][nextX]]) // 이전에 기록했던 현재기준 가장 외각섬이면 (부모)
                {
                    curParent = arr[nextY][nextX];
                }
                else // 이전에 기록된적 없는, 즉 내부의 섬이면서 이미 탐색했던거
                {
                    graph[curParent].push_back(arr[nextY][nextX]);
                }
 
                tempVistiedIslands[arr[nextY][nextX]] = true;
            }
            else if (arr[nextY][nextX] == 0)
            {
                visited[nextY][nextX] = true;
                q.push({ nextY,nextX });
            }
        }
    }
 
    for (int i = 0; i < graph[curParent].size(); ++i)
    {
        isOutermostIslands[graph[curParent][i]] = true;
    }
}
 
int GetMaxHeight(int island, int height)
{
    if (graph[island].size() == 0) return height;
    else
    {
        int maxNum = 0;
 
        for (int i = 0; i < graph[island].size(); ++i)
        {
            int next = graph[island][i];
 
            if (dp[next] != -1) continue;
 
            dp[next] = GetMaxHeight(next, 0);
            maxNum = max(maxNum, dp[next]);
            answers[dp[next]] += 1;
        }
 
        return maxNum + 1;
    }
}
 
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> r >> c;
 
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            cin >> input[i][j];
 
            if (input[i][j] == 'x') arr[i][j] = -1;
        }
    }
 
    int mark = 0;
 
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            if (arr[i][j] != -1) continue;
            
            ++mark;
            Update(i, j, mark);
 
            if (IsEdge(i, j)) isOutermostIslands[mark] = true;
        }
    }
 
    if (mark == 0)
    {
        cout << -1;
        return 0;
    }
 
    // 가장 바깥쪽 섬들 검출.
    for (int i = 0; i < r; ++i) 
    {
        for (int j = 0; j < c; ++j)
        {
            if (IsEdge(i, j) && arr[i][j] == 0 && !visited[i][j])
            {
                FindOutermostIslands(i, j);
            }
        }
    }
 
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            if (arr[i][j] == 0 && !visited[i][j]) // 바다 && 아직 방문못한곳
            {
                ConnectIslandsInheritance(i, j);
            }
        }
    }
 
    for (int i = 1; i <= mark; ++i)
    {
        if (dp[i] != -1) continue;
        dp[i] = GetMaxHeight(i, 0); // i번 섬의 최대높이를 dp[i]에 저장.
        answers[dp[i]] += 1;
    }
    
    for (int i = 0; i <= c; ++i)
    {
        if (answers[i] >= 1) cout << answers[i] << ' ';
        else break;
    }
 
    return 0;
}

여지껏 풀어본 문제중엔 등급이 제일 높은 문제다.

그래도 바로 이전에 BFS문제를 풀었던 터라, 탄력(?) 받아서 풀려고 했는데 당연히 쉽지는 않았다.

근데 그래도 결국 내힘으로 풀긴해서... 살다보니 이런날도 오나 싶었다.

 

일단 내 코드같은 경우는 일단 input은 string이긴 한데, 숫자로 하는게 편해서 int형으로 다시 라벨링했다.

그리고 전체적인 로직의 큰 틀은 다음과 같다.

 

1. 각 섬을 구한다. (함수명 Update)

2. 가장 바깥쪽에 위치한 섬을 구한다. 그러기 위해 외각에 위치한 '바다'에서 탐색을 수행한다.

     -> 이때 바다에 해당하는 곳은 전부 방문표시를 해줘야 한다.

3.  이후 다시 arr[i][j]를 순회하면서 '방문표시 안한 바다'부터 탐색을 수행한다. 

         -> 이때 '방문표시 안한 바다'란, 현재 제일 외각에 있는 섬과 그 안쪽에 있는 섬 사이의 바다를 의미한다.

         -> 그렇기 때문에 해당 바다에서 탐색을 수행했을 때 이미 외각으로 등록된 섬 이외의 섬을 만난다면, 해당 섬은 외각으로 등록된 섬의 내부에 있다는 것이다. 그렇기 때문에 외각섬의 자식으로 등록해준다.

         -> 해당 탐색이 끝난 후, 탐색해서 발견했던 자식섬들도 전부 외각섬에 등록해준다.(== 이전에방문했던 섬이라 생각해도됨)

 

4. 일련의 과정들을 마치면 각 섬의 관계들이 인접리스트형식으로(변수 graph) 저장되어있다. 이 인접리스트를 이용해서 각 높이의 개수들을 구하면 된다. 기본적으로 DFS를 차용했으며, 한번 해당 섬에대해서 수행할 때 결과값이 저장되기 때문에, dp값에 기록해놓고 다른곳의 불필요한 접근을 막는다. 

    -> 근데 아마 안하더라도 통과는 되긴할 것 같지만, 0ms로 통과는 안될지도? 문제에서의 섬개수가 아마 최대 1300개를 안넘을 것으로 예상된다.