백준 3197번 백조의 호수 C++

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

 

매번 빙판이 녹는것과 백조가 만날 수 있는지를 bfs를 돌리면 시간초과가 난다.

그렇기 때문에 각 구역마다 번호를 지정해두고 유니온 파인드를 이용해 빙판이 녹아서 합쳐지면 두 구역을 합쳐주면서 백조가 같은 구역에 있는지를 검사하면 된다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int r, c;
int head = 0;

vector<vector<bool>> found;
vector<vector<pair<int, char>>> board;

vector<int> parent;
vector<int> height;

vector<int> targets;

int dRow[4] = { -1,0,1,0 };
int dCol[4] = { 0,1,0,-1 };

int GetParent(int n) {
    if (n == parent[n])
        return n;
    return parent[n] = GetParent(parent[n]);
}

void Merge(int u, int v) {
    u = GetParent(u);
    v = GetParent(v);

    if (u == v)
        return;

    if (height[u] > height[v])
        ::swap(u, v);

    parent[u] = v;

    if (height[u] == height[v])
        height[v]++;
}

void InitBfs(int row, int col) {

    queue<pair<int, int>> q;
    q.push({ row,col });
    found[row][col] = true;

    while (!q.empty()) {
        auto curr = q.front();
        q.pop();

        if (board[curr.first][curr.second].second == 'L')
            targets.push_back(head);

        board[curr.first][curr.second].first = head;

        for (int i = 0; i < 4; i++) {
            int nextRow = curr.first + dRow[i];
            int nextCol = curr.second + dCol[i];
            if (nextRow < 0 || nextRow >= r) continue;
            if (nextCol < 0 || nextCol >= c) continue;
            if (board[nextRow][nextCol].second == 'X') continue;
            if (found[nextRow][nextCol]) continue;

            found[nextRow][nextCol] = true;
            q.push({ nextRow,nextCol });
        }
    }

    head++;
}

void Bfs(int row, int col, vector<pair<int, int>> &tmpFounds) {
    set<pair<int, int>> melts;

    int currHead = board[row][col].first;

    queue<pair<int, int>> q;
    q.push({ row,col });
    found[row][col] = true;

    while (!q.empty()) {
        auto curr = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nextRow = curr.first + dRow[i];
            int nextCol = curr.second + dCol[i];
            if (nextRow < 0 || nextRow >= r) continue;
            if (nextCol < 0 || nextCol >= c) continue;
            if (board[nextRow][nextCol].second == 'X') {
                melts.insert({ nextRow,nextCol });
                for (int j = 0; j < 4; j++) {
                    int nnextRow = nextRow + dRow[j];
                    int nnextCol = nextCol + dCol[j];
                    if (nnextRow < 0 || nnextRow >= r) continue;
                    if (nnextCol < 0 || nnextCol >= c) continue;
                    if (board[nnextRow][nnextCol].second != 'X') {
                        Merge(currHead, board[nnextRow][nnextCol].first);
                    }
                }
                continue;
            }
            if (found[nextRow][nextCol]) continue;

            found[nextRow][nextCol] = true;
            q.push({ nextRow,nextCol });
        }
    }

    for (auto a : melts) {
        found[a.first][a.second] = true;
        tmpFounds.push_back({ a.first,a.second });
        board[a.first][a.second] = { currHead,'.' };
    }

}

void RefreshFound() {
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            found[i][j] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> r >> c;
    found = vector<vector<bool>>(r, vector<bool>(c, false));
    board = vector<vector<pair<int, char>>>(r, vector <pair<int, char>>(c));
    for (int i = 0; i < r; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < c; j++) {
            board[i][j] = { -1,str[j] };
        }
    }

    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (board[i][j].second == 'X') continue;
            if (found[i][j]) continue;
            InitBfs(i, j);
        }
    }
    parent = vector<int>(head);
    height = vector<int>(head, 1);
    for (int i = 0; i < head; i++) {
        parent[i] = i;
    }

    RefreshFound();

    int cnt = 0;
    int target1 = targets[0];
    int target2 = targets[1];
    vector<pair<int, int>> tmpFounds;
    while (true) {
        if (GetParent(target1) == GetParent(target2))
            break;

        if (cnt == 0) {
            for (int i = 0; i < r; i++) {
                for (int j = 0; j < c; j++) {
                    if (board[i][j].second == 'X') continue;
                    if (found[i][j]) continue;
                    Bfs(i, j, tmpFounds);
                }
            }
        }
        else {
            vector<pair<int, int>> tmp;
            for (auto a : tmpFounds) {
                tmp.push_back({ a.first, a.second });
                found[a.first][a.second] = false;
            }
            tmpFounds.clear();

            for (auto a : tmp) {
                Bfs(a.first, a.second, tmpFounds);
            }
        }

        cnt++;
    }
    cout << cnt;
}