3197번 백조의 호수

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

# 시간 초과 # 복습 # bfs # 이분 탐색 # 생각 # 아이디어 # queue # 팁 tip

깨달은 점 : 행과 열이 100 이상이면 퍼져나가는 시점을 기록하는 방법을 써보자.

얼음을 한 번 녹일 때마다, bfs로 탐색해서 검사하는 것은 시간 초과가 발생한다.

그래서 시간을 줄이려면 queue를 여러 개 사용해서 구현하거나 약간의 아이디어가 필요하다.

우선 내 코드에서의 핵심은 Map[행][열] 배열이다.

1. 우선 'L'이나 '.'를 melt_queue에 push하여, 최대로 얼음을 녹이는 시점을 구한다.(모든 얼음이 다 녹는 시점)

2. 위에서 최대 시점을 구할 때, Map[행][열] 배열에 각 위치에 맞는 얼음이 녹이는 시점을 기록한다.(87번 째 줄 코드)

3. 1에서 구한 최대 시점을 기준으로 이분 탐색을 실행한다.

4. mid가 Map[y][x]보다 작다는 것은 시점이 mid일 때, Map[y][x]가 아직 녹지 않은 얼음이다.

위의 방법 말고 queue를 여러 개 사용하는 방법이 있다.

1. 우선 한 백조에서 다른 백조로 가는 bfs를 실행하면서, 인접하게 만나는 'X'(얼음)를 큐1에 담는다.

이 큐1은 후에 다시 1에서 활용할 것이다.

2. 그 다음 얼음을 녹인다.

1, 2를 하나의 과정으로 보고 진행한다.

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 1502
 
int R, C;
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
int Map[Max][Max];
bool visit[Max][Max];
char m[Max][Max];
queue<pair<int, int> > melt_queue;
pair<int, int> L[2];
 
// 백조끼리 만날 수 있는지 검사(BFS)
bool chk(int Limit)
{
    memset(visit, false, sizeof(visit));
    queue<pair<int, int> > q;
 
    q.push({ L[0].first, L[0].second });
    visit[L[0].first][L[0].second] = true;
 
    while (!q.empty())
    {
        int qs = q.size();
 
        while (qs--)
        {
            int r = q.front().first;
            int c = q.front().second;
 
            q.pop();
 
            if (r == L[1].first && c == L[1].second) {
                return true;
            }
 
            for (int i = 0; i < 4; i++) {
                int y = r + dy[i];
                int x = c + dx[i];
 
                // Map[y][x]가 Limit보다 크다는 것은 Limit 시점에서 Map[y][x]는 'X'라는 의미임.
                if (y < 0 || y >= R || x < 0 || x >= C || visit[y][x] || Map[y][x] > Limit) {
                    continue;
                }
 
                visit[y][x] = true;
                q.push({ y, x });
            }
        }
    }
 
    return false;
}
 
// 얼음이 다 녹는 시점 및 Map[행][열]에 각 얼음이 녹는 시점을 기록
int max_melt()
{
    int ret = 0;
 
    while (!melt_queue.empty())
    {
        int mqs = melt_queue.size();
 
        while (mqs--)
        {
            int r = melt_queue.front().first;
            int c = melt_queue.front().second;
 
            melt_queue.pop();
 
            for (int i = 0; i < 4; i++) {
                int y = r + dy[i];
                int x = c + dx[i];
 
                if (y < 0 || y >= R || x < 0 || x >= C || visit[y][x]) {
                    continue;
                }
 
                // m[y][x]가 무엇인지 상관없다.
                // 이유는 어차피 입력할 때 '.'과 'L'만 melt.queue에 push 하였기 때문에 
                // 점점 퍼져 나가서 ret + 1을 기록한다는 것으로만 이해하면 된다.
                // X가 있다면 그 부분으로 자동으로 퍼질 것이다.
                visit[y][x] = true;
                Map[y][x] = ret + 1;
                melt_queue.push({ y, x });        
            }
        }
 
        ++ret;
    }
 
    return ret;
}
 
// 이분 탐색
int bt(int Start, int End)
{
    int Left = Start, Right = End, ret = INT32_MAX;
 
    // '<' 아니다.
    while (Left <= Right)
    {
        int mid = (Left + Right) / 2;
 
        // 최솟값을 찾는다.
        if (chk(mid)) {
            ret = min(ret, mid);
            Right = mid - 1;
        }
        else {
            Left = mid + 1;
        }
    }
 
    return ret;
}
 
int main()
{
    cin.tie(0);
    cin >> R >> C;
 
    int idx = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> m[i][j];
            if (m[i][j] == 'L') {
                L[idx++] = { i, j };
            }
 
            if (m[i][j] == 'L' || m[i][j] == '.') {
                visit[i][j] = true;
                melt_queue.push({ i, j });
            }
        }
    }
 
    int Limit = max_melt();
 
    printf("%d\n", bt(0, Limit));
 
    return 0;
}