[Algorithm] Baekjoon 3197번 : 백조의 호수

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

3197번: 백조의 호수

struct Node
{
    int y;
    int x;
};
 
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int r, c;
int arr[1501][1501] = { 0 };
bool visited[1501][1501] = { false };
int meltDay = 0;
int swanDay = 0;
vector<Node> swans;
vector<Node> prevAddedNodes;
 
bool CheckMeeting()
{
    prevAddedNodes.push_back({ swans[0].y,swans[0].x });
 
    while (!prevAddedNodes.empty())
    {
        ++swanDay;
 
        queue<Node> q;
 
        for (int i = 0; i < prevAddedNodes.size(); ++i)
        {
            q.push(prevAddedNodes[i]);
            visited[prevAddedNodes[i].y][prevAddedNodes[i].x] = true;
        }
 
        prevAddedNodes.clear();
 
        while (!q.empty())
        {
            int curY = q.front().y;
            int curX = q.front().x;
            q.pop();
 
            if (curY == swans[1].y && curX == swans[1].x)
            {
                return true;
            }
 
            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] <= swanDay + 2) 
                {                                      
                    q.push({ nextY,nextX });
                    visited[nextY][nextX] = true;
                }
                else if (arr[nextY][nextX] == swanDay + 3) // 현재날짜의 얼음을 만난다면
                {
                    prevAddedNodes.push_back({ nextY,nextX }); 
                    visited[nextY][nextX] = true;
                }
            }
        }
    }
    
 
    return false;
}
 
 
void Melt()
{
    while (!prevAddedNodes.empty())
    {
        ++meltDay;
 
        queue<Node> q;
 
        for (int i = 0; i < prevAddedNodes.size(); ++i)
        {
            q.push(prevAddedNodes[i]);
        }
 
        prevAddedNodes.clear();
 
        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 (arr[nextY][nextX] == meltDay + 2) continue; // 같은날 녹은거면
 
                if (arr[nextY][nextX] == 0 || arr[nextY][nextX] == 2) 
                {
                    q.push({ nextY,nextX }); // 얼음찾을때까지 탐색.
                    arr[nextY][nextX] = meltDay + 2;
                }
                else if (arr[nextY][nextX] == 1) // 얼음이면
                {
                    arr[nextY][nextX] = meltDay + 2; // 물로 녹이기 (접근 불가능한)
                    prevAddedNodes.push_back({ nextY,nextX });
                }
            }
        }
    }
    
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> r >> c;
 
    for (int i = 0; i < r; ++i)
    {
        for (int j = 0; j < c; ++j)
        {
            char temp;
            cin >> temp;
 
            if (temp == '.')
            {
                arr[i][j] = 0;
                prevAddedNodes.push_back({ i,j });
            }
            else if (temp == 'X')
            {
                arr[i][j] = 1;
            }
            else
            {
                arr[i][j] = 2;
                swans.push_back({ i,j });
                prevAddedNodes.push_back({ i,j });
            }
        }
    }
 
    Melt();
    CheckMeeting();
 
    cout << swanDay;
}

시간줄이는걸 잘해야 하는 문제.

즉, 필요한만큼의 노드만 생성을 해야 한다.

각 날마다 녹은 얼음에 대해서 별도의 버퍼큐에 보관한다. 나같은 경우 걍 prevAddedNodes라는 벡터에다가 보관했다.

그리고 다음날 얼음을 녹이기 위한 탐색을 할 떄 딱 그 버퍼큐에 있는 노드들에 한해서만 탐색을 진행한다.

기존에 탐색했던 물부분이라던가 얼음부분에 대해서는 새롭게 탐색할 필요가 없다. 이부분을 명심하자.

이전 부분들도 탐색하려 할 경우 시간초과에 걸리거나 큐에 노드가 너무 들어가서 메모리초과가 발생하게 된다.

얼음을 녹일 때, 현재날짜에 기반해서 arr에다가 녹인날짜를 기록한다. 나같은 경우 현재날짜 +2를 기록했다.

이런식으로 Melt를 끝내면 arr에 각 얼음이 녹은날짜가 3부터시작해서 예쁘게 표시되어있다.

 

이걸 기반으로 백조의 길찾기를 수행한다. 마찬가지로 1일부터 시작하게 되는데, arr[nextY][nextX]의 값이 현재날짜 +2 '이하'라면, 얼음을 찾을 때까지 (얼음은 현재날짜 + 3) 탐색을 진행한다. 이 탐색을 진행하다 다른 백조를 만나면 끝이다.

 

만약 얼음을 만나면 얼음을 녹일때와 마찬가지로 해당 좌표노드들을 버퍼큐에 넣는다. (당연 현재 큐에는 넣으면 안된다)

 

이런식으로 필요한만큼의 노드만 큐에 넣는게 중요하다.

 

사실 나같은경우 예전부터 은연중에 필요한 노드들만 사용하기위해 prevAddedNodes를 사용하긴 했었는데, 내가 이걸 녹이는데에만 쓰고 백조탐색에는 적용 안해서 시간초과가 나왔었다.