문제

문제 링크

해설

• 【얼음을 녹인다 -> 백조가 만나는지 확인한다 -> 못 만났다면 반복한다.】 로직을 반복하면 풀 수 있습니다.
• 첫 장애물은 동시성 입니다.
  • '얼음'을 기준으로 얼음을 녹일 시 방금 녹은 얼음이 지금 녹을 예정인 얼음에 영향을 줄 수 있기 때문에 이 문제는 '물'을 기준으로 얼음을 녹여야 합니다.
  • 다시 말해서, 방금 녹은 얼음을 물로 표시할 경우, 인접한 얼음은 방금까지 얼음이었던 물 때문에 또다시 녹는 동시성 문제가 발생할 수 있다는 것입니다.
• 두 번째 장애물은 백조 입니다.
  • 문제에서 명확하게 따로 강조하지 않아 자칫 그냥 넘어갈 수 있는 함정(?)입니다.
  • 백조는 '물' 위에만 있을 수 있기 때문에, 백조의 위치는 '물'로 취급해야 합니다.
  • 즉, 백조의 위치를 기준으로 4방향에 있는 얼음은 다음 시간에 녹습니다.
• 세 번째 장애물은 시간 입니다.
  • 이 문제를 일반적인 DFS 또는 BFS로 풀면, 답은 제대로 잘 나오지만 반드시 시간초과에 걸립니다.
  • 1500×1500 크기의 2차원 배열에서 최선을 다해 녹는 얼음만을 추려내 DFS/BFS를 해 최대한 효율적으로 하려고 해도 O(N²)에 각 경우의 수마다 DFS/BFS를 수행하기 때문에 시간초과에 걸립니다.
  • 이 문제는 '이전 DFS/BFS 수행결과를 다시 이용할 수 있어야' 합니다.
  • 즉, 매번 두 백조 중 한 백조의 위치부터 DFS/BFS를 시작하는 것이 아니라, 이전에 얼음 때문에 못 갔던 좌표를 따로 저장해둔 뒤, 그 지점부터 DFS/BFS를 하는 것입니다.
  • 그러면, 적어도 그 지점까지의 DFS/BFS는 반복하지 않아도 됩니다.
• (BFS를 한다는 가정하에) 어떤 백조를 시작점으로 BFS 진행했을 때 얼음 때문에 더 이상 진행할 수 없을 때, 해당 얼음은 물과 닿는 '최외곽 좌표'입니다. 이 좌표들을 물로 바꿔 녹인 뒤 큐에 따로 저장합니다.
• 다음 loop에서는 방금 저장해둔 좌표부터 다시 BFS를 시작합니다.
  • 이때 다른 백조를 만났다면, 정답을 출력하면 되고,
  • 얼음을 만났다면, 따로 만들어둔 큐에 저장해서 다음 loop를 대비하고,
  • 물을 만났다면, 더 이동하면 됩니다.

코드

#include <iostream>
#include <queue>
using namespace std;

constexpr int MAX = 1501;
constexpr int d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

int R, C;
char lake[MAX][MAX];
bool visited_water[MAX][MAX], visited_swan[MAX][MAX];
queue<pair<int, int>> water_q, swan_q;

inline bool is_not_valid(int y, int x) {
    return (y < 0 || x < 0 || y >= R || x >= C);
}

bool is_they_meet(queue<pair<int, int>>& q)
{
    while (!swan_q.empty()) {
        int cy = swan_q.front().first, cx = swan_q.front().second;
        swan_q.pop();
        for (auto i : d) {
            int ny = cy + i[0], nx = cx + i[1];
            if (is_not_valid(ny, nx) || visited_swan[ny][nx]) continue;
            visited_swan[ny][nx] = true;
            // 백조가 이동한 좌표가 '물'이면 현재 큐에, '얼음'이면 다음 큐에 삽입.
            if (lake[ny][nx] == '.') swan_q.emplace(ny, nx);
            else if (lake[ny][nx] == 'X') q.emplace(ny, nx);
            else if (lake[ny][nx] == 'L') return true;
        }
    }
    return false;
}

void melt_ice(queue<pair<int, int>>& q)
{
    while (!water_q.empty()) {
        int cy = water_q.front().first, cx = water_q.front().second;
        water_q.pop();
        for (auto i : d) {
            int ny = cy + i[0], nx = cx + i[1];
            if (is_not_valid(ny, nx) || visited_water[ny][nx] || lake[ny][nx] != 'X') continue;
            visited_water[ny][nx] = true;   // 중복 큐 삽입 회피.
            q.emplace(ny, nx);              // 다음 시간(초)을 위해 다음 큐에 삽입.
            lake[ny][nx] = '.';             // 얼음 녹음.
        }
    }
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> R >> C;

    int swan_sy, swan_sx;
    for (int y = 0; y < R; y++) {
        for (int x = 0; x < C; x++) {
            cin >> lake[y][x];
            if (lake[y][x] != 'X') {
                // [주의] 백조도 물로 취급해야 합니다.
                if (lake[y][x] == 'L') swan_sy = y, swan_sx = x;
                water_q.emplace(y, x);
                visited_water[y][x] = true;
            }
        }
    }
    swan_q.emplace(swan_sy, swan_sx);       // 백조(둘 중 하나) 시작위치 삽입
    visited_swan[swan_sy][swan_sx] = true;  // 방문 표시

    int answer = 0;
    while (true) {
        queue<pair<int, int>> swan_nextq, water_nextq;
        if (is_they_meet(swan_nextq)) break;
        melt_ice(water_nextq);
        water_q = std::move(water_nextq);
        swan_q = std::move(swan_nextq);
        answer++;
    }
    cout << answer << '\n';
    return 0;
}

• queue의 복사를 조금 더 효율적으로 하기 위해 다음 loop를 위한 queue는 반복문 내부에 local 변수로 선언한 뒤 std::move를 이용해서 우측값 이동을 이용해 복사생성자 호출을 막았습니다.

소스코드 링크

결과