백조의 호수 - 3197

//3197 - 백조의 호수
 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int N, M;
int arr[1500][1500];
int xarr[4] = {0, 0, 1, -1};
int yarr[4] = {1, -1, 0, 0};
vector<int> X;
vector<int> Y;
queue<int> qx[2], qy[2];
vector<vector<bool>> check;
 
struct DisjointSet
{
    vector<int> parent, rank;
 
    DisjointSet(int n) : parent(n), rank(n, 1)
    {
        for(int i = 0; i<n; ++i)
            parent[i] = i;
    }
 
    int find(int u)
    {
        if(u == parent[u]) return u;
        return parent[u] = find(parent[u]);
    }
 
    void merge(int u, int v)
    {
        u = find(u); v = find(v);
        if(u == v) return;
        if(rank[u] > rank[v]) swap(u, v);
        parent[u] = v;
        if(rank[u] == rank[v]) ++rank[v];
    }
};
 
int convert(int x, int y)
{
    return 1 + x*M+y;
}
 
void aroundMerge(int x, int y, DisjointSet& set)
{
    for(int i = 0; i<4; ++i)
        if(x+xarr[i] >= 0 && x+xarr[i] < N && y+yarr[i] >= 0 && y+yarr[i] < M)
            if(arr[x+xarr[i]][y+yarr[i]] == '.')
                set.merge(convert(x, y), convert(x+xarr[i], y+yarr[i]));
}
 
void init(DisjointSet& set)
{
    check = vector<vector<bool>>(N, vector<bool>(M, false));
    string s;
    for(int i = 0; i<N; ++i)
    {
        cin >> s;
        for(int j = 0; j<M; ++j)
            arr[i][j] = s[j];
    }
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
        {
            if (arr[i][j] != 'X')
            {
                qx[0].push(i), qy[0].push(j), check[i][j] = true;
                aroundMerge(i, j, set);
            }
            if (arr[i][j] == (int)'L')
                X.push_back(i), Y.push_back(j), arr[i][j] = '.';
        }
}
 
void change(int x, int y, int qidx, DisjointSet& set)
{
    if (x >= 0 && x < N && y >= 0 && y < M)
        if (arr[x][y] == 'X' && !check[x][y])
        {
           check[x][y] = true, qx[qidx].push(x), qy[qidx].push(y);
           arr[x][y] = '.';
           aroundMerge(x, y, set);
        }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    DisjointSet set(N*M+1);
    init(set);
    int ans = 0;
    int qidx = 0;
    while (true)
    {
        while (!qx[qidx].empty())
        {
            int x = qx[qidx].front();
            qx[qidx].pop();
            int y = qy[qidx].front();
            qy[qidx].pop();
            for (int k = 0; k < 4; ++k)
                change(x + xarr[k], y + yarr[k], (qidx + 1) % 2, set);
        }
        ++ans;
        if(set.find(convert(X[0], Y[0])) == set.find(convert(X[1], Y[1])))
            break;
        qidx = (qidx + 1) % 2;
    }
    cout << ans;
}

 

 

 

 

 

 

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

3197번: 백조의 호수

 

 

 

 

 

 

백조의 호수

두가지 부분문제로 나눌수 있습니다.

 

1. 얼음 녹이기

queue를 이용해 인접한 얼음을 녹일수 있는 후보들을 저장해 매 단계마다

인접 얼음을 녹이고, 녹은 얼음은 다음 단계에서 인접 얼음을 녹일수 있는 후보이니 queue에 채워 넣었습니다.

2. 두 백조가 만나는지 확인하기

단방향 bfs탐색으로는 시간초과가 나서 다른 방법을 찾다 union-find를 이용해 확인했습니다.

맨 초기 단계에 연못상태에선 서로 이어진 물끼리 같은집합, 얼음은 모두 각자의 집합을 가지게 하고, 매 단계가 진행될때마다 물이된 얼음의 인접한 곳을 모두 확인해 물인것들을 모두 merge해 연결된 물들을 같은 집합에 넣고, 두 백조의 위치가 같은 집합에 포함되어 있는지 확인했습니다.

(양방향 bfs탐색으로 해결되는지 나중에 한번 해보겠습니다..)