[BOJ] 백조의 호수(3197)

[백준(BOJ)] 백조의 호수(3197) C++

문제 : BOJ_3197번 백조의 호수

문제 설명

이분탐색, bfs

물 공간과 빙판 공간이 있는 지도가 주어지고, L에 두 백조의 위치가 주어집니다.

물 공간과 가로, 세로로 접한 빙판 부분이 하루에 한 번씩 녹는데, 이때 두 백조가 만날 수 있는 최소의 날을 계산하는 문제입니다.

이 문제는 하루에 한 번씩 녹는 빙판 부분도 고려해야 하고, 또 빙판이 녹았을 때 만날 수 있는 최소의 날도 구해야 하기 때문에 bfs와 이분 탐색 두 가지가 쓰이는 문제입니다.

---

Solution

처음에 bfs를 이용하여 빙판이 모두 녹는 최대 날을 이분 탐색의 max 값으로 지정해 주고 이분 탐색을 실행합니다.

최솟값과 최댓값의 중간값으로 bfs를 돌리며 중간값의 날이 되기 전에 백조를 만난다면 최솟값을 올려주고, 만나지 못한다면 최댓값을 낮춰주며 이분 탐색을 진행했습니다.

이렇게 구한 최적해가 두 백조가 만날 수 있는 최소의 날입니다.

---

Description

• 두 백조의 위치를 vector<pair<int, int>> v로 선언하여 표현했습니다.
• 특정 위치를 방문한 횟수를 vis 배열로 체크했고, 방문 여부를 확인하기 위해 -1로 초기화하고 시작했습니다.
• vis의 -1 초기화는 memset을 이용했습니다.

---

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
char map[1501][1501];
int vis[1501][1501];
int now_vis[1501][1501];
vector<pair<int, int>> v;
void bfs(void);
int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };
int r, c;
int le = 0;
int ri = 1500 * 2+1;
int res_max = 0;
queue<pair<int, int>> q;
int main(void) {
    memset(vis, -1, sizeof(vis));
    scanf("%d%d", &r, &c);
    for (int i = 1; i <= r; i++) {
        for (int j = 1; j <= c; j++) {
            scanf(" %c", &map[i][j]);
            if (map[i][j] == '.') {
                vis[i][j] = 0;
                q.push({ i,j });
                now_vis[i][j] = 1;
            }
            else if (map[i][j] == 'L') {
                v.push_back({ i,j });
                vis[i][j] = 0;
                q.push({ i,j });
                now_vis[i][j] = 1;
            }
        }
    }
    bfs();
    ri = res_max;
    while (le <= ri) {
        memset(now_vis, 0, sizeof(now_vis));
        now_vis[v[0].first][v[0].second] = 1;
        int swc = 0;
        int mi = (le + ri) / 2;
        queue<pair<int, int>> res;
        res.push({ v[0].first,v[0].second });
        while (!res.empty()) {
            int x = res.front().first;
            int y = res.front().second;
            res.pop();
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx<1 || ny<1 || nx>r || ny>c) continue;
                if (nx == v[1].first && ny == v[1].second) {
                    swc++;
                    break;
                }
                if (vis[nx][ny] > mi) continue;
                if (now_vis[nx][ny]) continue;
                now_vis[nx][ny] = 1;
                res.push({ nx,ny });
            }
        }
        if (swc) ri = mi - 1;
        else le = mi + 1;
    }
    printf("%d\n", le);
}
void bfs(void) {
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx<1 || ny<1 || nx>r || ny>c) continue;
            if (map[nx][ny] == 'L') continue;
            if (now_vis[nx][ny]) continue;
            if (vis[nx][ny] == -1) {
                vis[nx][ny] = vis[x][y] + 1;
                res_max = max(res_max, vis[nx][ny]);
                now_vis[nx][ny] = 1;
                q.push({ nx,ny });
            }
        }
    }
}