백준 3197 백조의 호수

1. 이분 탐색하는 방법 2. 빠르게 찾는 방법을 생각해보기 3. 물맵을 만들어서, 몇분후에 얼마나 갈 수 있는지 저장합니다. 4. 이분탐색을 통해서, 갈 수 있는지 없는지를 판단합니다. 5 그리고 이분탐색 쭉쭉 줄여나가다가 st 를 출력하면 됩니다.

#include <iostream>
#include <cstdio>
#include <queue>
 
using namespace std;
int N, M;
#define SIZE 18 // 1501
char map[SIZE][SIZE];
int L[2][2];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int visit[SIZE][SIZE];
int water[SIZE][SIZE];
int index;
int st, en;
struct point {
    int x, y;
};
queue<point> que;
int x, y, nx, ny;
 
void problemIn() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> map[i];
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 'L') {
                L[index][0] = i;
                L[index][1] = j;
                index++;
            }
        }
    }
}
 
void clear(int arr[SIZE][SIZE]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            arr[i][j] = 0;
        }
    }
}
 
int waterbfs() {
    int cnt = 1;
    int ret = 0;
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == '.' || map[i][j] == 'L') {
                visit[i][j] = 1;
                que.push({ i,j });
            }
        }
    }
 
    while (!que.empty()) {
        int qlen = que.size();
        while (qlen--) {
            x = que.front().x;
            y = que.front().y;
            que.pop();
            for (int i = 0; i < 4; i++) {
                nx = x + dx[i];
                ny = y + dy[i];
                if (nx < 0 || ny < 0 || nx >= N || ny >= M || visit[nx][ny]) continue;
                if (map[nx][ny] != 'L') {
                    water[nx][ny] = cnt;
                    visit[nx][ny] = 1;
                    que.push({ nx,ny });
                }
            }
        }
        cnt++;
    }
    return cnt - 2;
}
 
bool bfs(int limit) {
 
    que.push({ L[0][0], L[0][1] });
    visit[L[0][0]][L[0][1]] = 1;
    while (!que.empty()) {
        x = que.front().x;
        y = que.front().y;
        que.pop();
 
        if (x == L[1][0] && y == L[1][1]) return true;
        for (int i = 0; i < 4; i++) {
            nx = x + dx[i];
            ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= N || ny >= M || visit[nx][ny]) continue;
            if (water[nx][ny] <= limit) {
                que.push({ nx,ny });
                visit[nx][ny] = 1;
            }
        }
    }
    return false;
}
 
void solve() {
    en = waterbfs();
    while (st <= en) {
        clear(visit);
        int mid = (st + en) / 2;
        if (bfs(mid)) en = mid - 1;
        else st = mid + 1;
    }
}
 
int main() {
    problemIn();
    solve();
    cout << st << endl;
    return 0;
}