백준 3197번: 백조의 호수 / C++

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

3197번: 백조의 호수

---

확실하게 플래티넘 문제는 평범하게 모든 경우의 수를 계산해서 문제를 해결하면 시간초과 문제가 발생한다. 이를 해결하기 위해서는 탐색시간을 줄이기 위한 방법을 찾아야 하는데  총 3가지 방법을 이용하여 시간을 단축하였다. 

첫번째 방법은 백조를 탐색할때는 이전에 탐색한 구역은 탐색을 하지않는 방법으로 탐색을 하였다. 두번째 방법으로는 입력을 받을때 이전 코드는 모든 입력을 받고 다시한번 전체를 탐색해서 다음날 녹을 빙하를 찾았는데 그럴필요없이 입력을 받는 과정에서 바로 다음날 녹을 빙하를 찾았다. 마지막이 가장 중요한 포인트인데 다음날 녹을 빙하를 하루마다 탐색을 하면 1500*1500 을 모두 탐색해야하기 때문에 다음날  녹을 빙하들만 큐에 넣어두고 다음날도 녹은 빙하 주변으로 탐색을 하여 시간을 단축하였다.

#include <iostream>
#include <queue>
using namespace std;
 
int R, C; // row, col
char arr[1500][1500]{};
queue<pair<int, int>> ice;
pair<int, int> LPos; // 백조 위치
bool visited[1500][1500]{};
bool visited2[1500][1500]{};
queue<pair<int, int>> memory;
 
bool BFS()
{
    queue<pair<int, int>> Q = memory;
    queue<pair<int, int>> Empty;
    memory = Empty;
    visited[LPos.first][LPos.second] = true;
    Q.push(make_pair(LPos.first, LPos.second));
 
    while (!Q.empty()) {
        int row = Q.front().first;
        int col = Q.front().second;
        // up row-1
        if (row > 0 && arr[row - 1][col] != 'X' && !visited[row - 1][col]) {
            if (arr[row - 1][col] == 'L')
                return true;
            Q.push(make_pair(row - 1, col));
            visited[row - 1][col] = true;
        }
        if (row > 0 && arr[row - 1][col] == 'X' && !visited[row - 1][col]) {
            memory.push(make_pair(row - 1, col));
            visited[row - 1][col] = true;
        }
        // down row+1
        if (row + 1 < R && arr[row + 1][col] != 'X' && !visited[row + 1][col]) {
            if (arr[row + 1][col] == 'L')
                return true;
            Q.push(make_pair(row + 1, col));
            visited[row + 1][col] = true;
        }
        if (row + 1 < R && arr[row + 1][col] == 'X' && !visited[row + 1][col]) {
            memory.push(make_pair(row + 1, col));
            visited[row + 1][col] = true;
        }
        // left col-1
        if (col > 0 && arr[row][col - 1] != 'X' && !visited[row][col - 1]) {
            if (arr[row][col - 1] == 'L')
                return true;
            Q.push(make_pair(row, col - 1));
            visited[row][col - 1] = true;
        }
        if (col > 0 && arr[row][col - 1] == 'X' && !visited[row][col - 1]) {
            memory.push(make_pair(row, col - 1));
            visited[row][col - 1] = true;
        }
        // right col+1
        if (col + 1 < C && arr[row][col + 1] != 'X' && !visited[row][col + 1]) {
            if (arr[row][col + 1] == 'L')
                return true;
            Q.push(make_pair(row, col + 1));
            visited[row][col + 1] = true;
        }
        if (col + 1 < C && arr[row][col + 1] == 'X' && !visited[row][col + 1]) {
            memory.push(make_pair(row, col + 1));
            visited[row][col + 1] = true;
        }
        Q.pop();
    }
    return false;
}
void NextDay()
{
    queue <pair<int, int>> next;
    while (!ice.empty())
    {
        int row = ice.front().first;
        int col = ice.front().second;
        arr[row][col] = '.';
        // up row-1
        if (row > 0 && arr[row - 1][col] == 'X' && !visited2[row - 1][col]) {
            visited2[row - 1][col] = true;
            next.push(make_pair(row - 1, col));
        }
        // down row+1
        if (row+1 < R && arr[row + 1][col] == 'X' && !visited2[row + 1][col]) {
            visited2[row + 1][col] = true;
            next.push(make_pair(row + 1, col));
        }
        // left col-1
        if (col > 0 && arr[row][col-1] == 'X' && !visited2[row][col-1]) {
            visited2[row][col-1] = true;
            next.push(make_pair(row, col-1));
        }
        // right col+1
        if (col+1 < C && arr[row][col+1] == 'X' && !visited2[row][col+1]) {
            visited2[row][col+1] = true;
            next.push(make_pair(row, col+1));
        }
        ice.pop();
    }
    ice = next;
}
 
void Solve()
{
    int ans = 0;
    while (!BFS()) {
        ++ans;
        // 하루가 지나서 빙하가 녹음
        NextDay();
    }
 
    cout << ans;
}
 
int main()
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> R >> C;
    for (int row = 0; row < R; ++row) {
        string str; cin >> str;
        for (int col = 0; col < C; ++col) {
            arr[row][col] = str[col];
            if (str[col] == 'L') { // 백조위치 기록
                LPos.first = row;
                LPos.second = col;
            }
 
            if (str[col] == '.' || str[col] == 'L') {
                // left col-1
                if (col > 0 && arr[row][col - 1] == 'X' && !visited2[row][col - 1]) {
                    visited2[row][col-1] = true;
                    ice.push(make_pair(row, col-1));
                }
                // up row-1
                if (row > 0 && arr[row-1][col] == 'X' && !visited2[row-1][col]) {
                    visited2[row-1][col] = true;
                    ice.push(make_pair(row-1, col));
                }
            }
            else if ((row > 0 && arr[row - 1][col] != 'X') ||
                (col > 0 && arr[row][col - 1] != 'X')) {
                visited2[row][col] = true;
                ice.push(make_pair(row, col));
            }
        }
    }
 
    Solve();
}