[3197] 백조의 호수

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

3197번: 백조의 호수

<문제>

naive하게 구현하면 시간초과가 나올 줄은 알고 있었다. 맵 크기가 1500*1500다.

그래서 처음에 구상한 방법은 "bfs를 사용한 전처리" + "이분탐색" 이였다.

 

이분탐색에 쓸 left는 0부터 시작하는 게 당연하다. 빙판이 아예 없으면 최적해가 0이기 때문이다.

right의 경우, n*n의 공간이 전부 빙판으로 채워졌다면 가장 늦게 녹는 빙판은, n/2정도의 시간이 걸린다.

상하좌우 모두에서 빙판이 녹기 시작하니, n이 아니라 n/2로 설정하면 되고, 이 문제에서는 751정도로 설정할 수 있다.

 

 bfs를 통해 아래의 2차원 배열을 구성해야 한다.

dp[i][j] : (i, j)노드로 가기 위한 최소턴

 

한 가지 (시간초과에) 유의할 점이라면 dp를 구할 때 memset을 사용해 대충 구현했는데 TLE가 나왔다.

이분탐색을 적용하면 TLE는 안 나올 줄 알았는데

memset을 제거하고 단 한 번만 bfs를 돌도록 변경해서야 AC를 받았다. 

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
typedef struct {
    int y, x;
} state;
int n, m, l, r, dp[1501][1501], dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
char a[1501][1501];
vector<state> pos;
queue<state> initq;
void init(void) {
    int i;
    while (!initq.empty()) {
        state cur = initq.front();
        initq.pop();
        for (i = 0; i < 4; i++) {
            int y = cur.y + dy[i];
            int x = cur.x + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m) continue;
            if (dp[y][x] == -1) {
                dp[y][x] = dp[cur.y][cur.x] + 1;
                initq.push({y, x});
                r = max(dp[y][x], r);
            }
        }
    }
    return;
}
bool check(int k) {
    bool vst[1501][1501];
    memset(vst, false, sizeof(vst));
    queue<state> q;
    int sy = pos[0].y, sx = pos[0].x;
    q.push({sy, sx});
    vst[sy][sx] = true;
    int i;
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        if (cur.y == pos[1].y && cur.x == pos[1].x) {
            return true;
        }
        for (i = 0; i < 4; i++) {
            int y = cur.y + dy[i];
            int x = cur.x + dx[i];
            if (y < 0 || x < 0 || y >= n || x >= m) continue;
            if (vst[y][x] == true || dp[y][x] > k) continue;
            vst[y][x] = true;
            q.push({y, x});
        }
    }
    return false;
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    memset(dp, -1, sizeof(dp));
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            cin >> a[i][j];
            if (a[i][j] == '.') {
                dp[i][j] = 0;
                initq.push({i, j});
            }
            if (a[i][j] == 'L') {
                dp[i][j] = 0;
                initq.push({i, j});
                pos.push_back({i, j});
            }
        }
    }
    init();
    int ans = 54321;
    while (l <= r) {
        int mid = (l + r) / 2;
        bool res = check(mid);
        if (res == true) {
            ans = min(mid, ans);
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans;
    return 0;
}