백준 3197 백조의 호수

문제 URL : https://www.acmicpc.net/problem/3197

3197번: 백조의 호수

문제 접근법 :  사이즈가 매우큽니다. 1500*1500 이기때문에

두백조를 기준으로 큐를잡아서 매번 bfs를도려 매일 마다 한칸씩 얼음을 녹이는건 너무 비효율적입니다.

최대한 연산을 줄이는 방법을 선택해야하는데

 

백조가 갈수있는 방향까지 움직입니다. 얼음을 만나면 

어차피 얼음은 녹지만 가장 바깥지점부터 녹습니다. 그렇다면 물을 기준으로 잡고 좌우 상하방향으로 움직여서 얼음을 만나게되면 백조가 다움직인후 얼음을 녹이면서 탐색을진행하면 됩니다.

 

소스코드 : 

 

#include<bits/stdc++.h>
using namespace std;
char board[1500][1500];
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
bool check[1500][1500];
vector<pair<int, int>> v;
int n, m;
queue<pair<int, int>> water;
void input() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> board[i][j];
            if (board[i][j] == 'L') {
                v.push_back({ i,j });
                board[i][j] = '.';
                water.push({ i,j });
            }
            else if (board[i][j] == '.') {
                water.push({ i,j });
            }
        }
    }
}
 
bool isrange(int y, int x) {
    return 0 <= y && y < n && 0 <= x && x < m;
}
 
int bfs() {
    queue<pair<int, int>> q;
    int cnt = 0;
    q.push(v[0]);
    check[v[0].first][v[0].second] = 1;
    while (true) {
        bool flag = false;
        queue<pair<int, int>> nq;
        while (!q.empty()) {
            int y, x;
            tie(y, x) = q.front();
            q.pop();
            if (y == v[1].first && x == v[1].second)
                return cnt;
 
            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (isrange(ny, nx)&&check[ny][nx]==0) {
                    check[ny][nx] = true;
                    if (board[ny][nx] == '.') {
                        q.push({ ny,nx });
                    }
                    else if (board[ny][nx] == 'X')
                        nq.push({ ny,nx });
                    
                }
            }
        }
        int watersize = water.size();
        while (watersize--) {
            int y, x;
            tie(y, x) = water.front();
            water.pop();
            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
                if (isrange(ny, nx) && board[ny][nx] == 'X') {
                    board[ny][nx] = '.';
                    water.push({ ny,nx });
                }
            }
        }
        q = nq;
        cnt++;
    }
    return cnt;
}
void solve() {
    cout << bfs() << "\n";
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    input();
    solve();
}
 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.