[Algorithm] Baekjoon 2573번 : 빙산

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

2573번: 빙산

struct Node
{
    int y;
    int x;
};
 
int row, col;
int arr[301][301];
bool visited[301][301];
int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
list<Node> icebergPositions;
int meltCheck = 0;
 
void melt()
{
    for (auto iter = icebergPositions.begin(); iter != icebergPositions.end(); )
    {
        int y = iter->y;
        int x = iter->x;
 
        if (y - 1 >= 0 && (arr[y - 1][x] <= 0 && arr[y - 1][x] >= meltCheck)) arr[y][x] -= 1;
        if (y + 1 < row && (arr[y + 1][x] <= 0 && arr[y + 1][x] >= meltCheck)) arr[y][x] -= 1;
        if (x - 1 >= 0 && (arr[y][x - 1] <= 0 && arr[y][x - 1] >= meltCheck)) arr[y][x] -= 1;
        if (x + 1 < col && (arr[y][x + 1] <= 0 && arr[y][x + 1] >= meltCheck)) arr[y][x] -= 1;
 
        if (arr[y][x] <= 0)
        {
            arr[y][x] = meltCheck - 1;
            iter = icebergPositions.erase(iter);
        }
        else
        {
            ++iter;
        }
    }
 
    --meltCheck;
}
 
pair<bool, int> checkTwoPiece()
{
    if (icebergPositions.size() <= 1)
    {
        return { false,0 };
    }
 
    memset(visited, false, sizeof(visited));
    int count = 1;
    int startY = icebergPositions.front().y;
    int startX = icebergPositions.front().x;
    queue<Node> q;
    q.push({ startY,startX });
    visited[startY][startX] = true;
 
    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 >= row) continue;
            if (nextX < 0 || nextX >= col) continue;
            if (visited[nextY][nextX]) continue;
            if (arr[nextY][nextX] <= 0) continue;
 
            visited[nextY][nextX] = true;
            ++count;
            q.push({ nextY,nextX });
 
        }
    }
 
    if (icebergPositions.size() != count) // 개수가 안맞다, 즉 한덩어리가 아니다
    {
        return { true,0 };
    }
    return { false,1 };
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int result = 0;
 
    cin >> row >> col;
 
    for (int i = 0; i < row; ++i)
    {
        for (int j = 0; j < col; ++j)
        {
            cin >> arr[i][j];
            if (arr[i][j] != 0)
            {
                icebergPositions.push_back({ i,j });
            }
        }
    }
 
    while (1)
    {
        pair<bool, int> check = checkTwoPiece();
 
        if (check.first)
        {
            cout << result;
            return 0;
        }
        else // 한덩어린데
        {
            if (check.second == 0) // 빙산이 다 녹았으면
            {
                cout << 0;
                return 0;
            }
        }
 
        melt();
        ++result;
    }
}

골드4짜리지만 생각할 게 좀 더 많은 녹이기 문제이다.

모든 빙산에 대해 녹이기함수(melt)를 수행할 때 반드시 melt를 호출하기 이전의 arr기준으로 검사 후, 녹여야한다는게 제일 중요하다. 

녹인 다음에는 녹았다고 arr에 체크를 해놓을텐데, 그 체크를 한 값이 다음 빙산을 녹일 때 영향을 절대로 줘서는 안된다.

 

일단 내 코드같은 경우, 먼저 빙산의 위치를 따로 저장해놓는다. 어차피 빙산위치만 검사할것이기 때문이다.

저장할 컨테이너는 list로 저장했다. 왜냐하면 melt한 이후에 녹아버린 빙산의 위치는 다음 melt때 검사할 필요가 없기 때문이다. 그래서 melt에서 각 빙산마다 녹이기를 시도한 후, 아예 녹아버린다면 해당 빙산을 컨테이너에서 빼버렸다.

 

즉, 반복문 도중에 삭제가 발생하기 때문에 vector보다는 list를 선택했다. list는 삽입,삭제의 수행속도가 상수시간이기 때문이다.

그리고 위 코드에서 제일 중요한 부분이 melt()함수 부분이다.

보면 알겠지만 meltCheck라는 int 변수를 따로 사용하고 있는것을 알 수 있다.

 

코드를 보면 melt에서 상,하,좌,우를 검사할 때 0이하 meltCheck 이상인 곳만 '바다'로 판단하는 것을 알 수 있다. (제일 중요) 

매번 melt를 수행하면서, 빙산이 녹아버린곳은 바다가 됐다는것을 다음 melt를 수행할 때 알리기 위해서이다.

처음에 말했지만, melt는 해당 함수 호출 전 arr을 기준으로 수행되어야만 하기 때문이다.

녹이기를 정상적으로 수행했다면 살아있는 빙산 아무거나 잡고 BFS를 수행해서 전체 빙산개수랑 일치하는지 체크하면 된다. 일치하지 않으면 한덩어리가 아닌것이니까 그대로 종료하면 되고 한덩어리면 1개이하될 때까지 전체로직을 반복하면 된다.

 

문제를 직접 풀어보면 알겠지만 일단 단순하게 접근하다보면 왜 독립적인 수행이 되어야하는지 알 것이다.

위 코드같은 경우 36ms가 나오는데, 꽤 효율적으로 짠 것 같다.

작성 이후에 같은 문제를 패스한 사람들의 수행속도를 비교했을 때, 한 5,6페이지 넘길때까지 내 수행속도보다 낮은것은 보지 못했다. 

물론 제일 잘 짠것은 아니겠지만, 이정도면 어떤 테스트케이스로 저격하든 시간초과가 날 것 같진 않다.