[백준 c++] 3197 백조의 호수

문제 설명

https://www.acmicpc.net/problem/3197
두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.
호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.
호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.
백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.
며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.

• 입력
  입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.
  다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.
• 출력
  첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

아이디어

얼음 녹이는 BFS, 백조가 이동하는 BFS로 푸는 문제다.
제한시간이 1초라서 처음 제출한 코드는 시간초과가 났다.
그래서 매번 모든 맵을 탐색하지 않고 직전날 녹았던 얼음을 버퍼 큐에 넣고
다음 날엔 그 버퍼 큐를 복사하여 사용했다.

탐색 중에 .는 일반 큐에 넣는다.
X를 만나면 버퍼 큐에 넣는다.
일반 큐가 비면 버퍼 큐의 값으로 복사하여 가져온다.

++ 주의할 점은 L도 물 공간으로 봐야한다는 것이다.

전체 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n, m, ly, lx, y, x, flag, p, q;
char c;
char a[1501][1501];
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, -1, 0, 1};
int m_visited[1501][1501];
int l_visited[1501][1501];
queue<pair<int, int>> map;
queue<pair<int, int>> buf;
queue<pair<int, int>> em;
queue<pair<int, int>> res;
queue<pair<int, int>> buf2;
void melt()
{
    while (map.size() || buf.size())
    {
        tie(y, x) = map.front();
        map.pop();
        for (int i = 0; i < 4; i++)
        {
            int ny = dy[i] + y;
            int nx = dx[i] + x;
            if (ny < 0 || nx < 0 || ny >= n || nx >= m)
                continue;
            if (m_visited[ny][nx])
                continue;
            if (a[ny][nx] == '.')
            {
                m_visited[ny][nx] = m_visited[y][x];
                map.push({ny, nx});
            }
            else if (a[ny][nx] == 'X')
            {
                m_visited[ny][nx] = m_visited[y][x] + 1;
                a[ny][nx] = '.';
                buf.push({ny, nx});
            }
        }

        if (map.size() == 0)
        {
            map = buf;
            buf = em;
            while (res.size())
            {
                tie(p, q) = res.front();
                res.pop();
                for (int i = 0; i < 4; i++)
                {
                    int yy = dy[i] + p;
                    int xx = dx[i] + q;
                    if (yy < 0 || xx < 0 || yy >= n || xx >= m)
                        continue;
                    if (l_visited[yy][xx])
                        continue;
                    if (a[yy][xx] == 'L')
                    {
                        flag = l_visited[p][q];
                        return;
                    }
                    if (a[yy][xx] == '.')
                    {
                        l_visited[yy][xx] = l_visited[p][q];
                        res.push({yy, xx});
                    }
                    if (a[yy][xx] == 'X')
                    {
                        l_visited[yy][xx] = l_visited[p][q] + 1;
                        buf2.push({yy, xx});
                    }
                }
            }
            res = buf2;
            buf2 = em;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
            if (a[i][j] == 'L')
            {
                ly = i;
                lx = j;
            }
            if (a[i][j] == '.' || a[i][j] == 'L')
            {
                m_visited[i][j] = 1;
                map.push({i, j});
            }
        }
    }
    res.push({ly, lx});
    l_visited[ly][lx] = 1;
    melt();

    cout << flag << "\n";
}