핵심 아이디어

<aside> 💡

원끼리 겹치면서 다음과 같이 벽들이 연결되면 $(n,m)$으로 이동할 수 없다.

• 위쪽 벽과 왼쪽 벽

• 오른쪽 벽과 아래쪽 벽

• 왼쪽 벽과 오른쪽 벽

• 위쪽 벽과 아래쪽 벽 </aside>

• 연결 여부는 분리집합(유니온파인드)를 이용하면 구할 수 있다.

• 두 원의 중심 간 거리가 두 원의 반지름 합보다 작거나 같으면 두 원은 연결된다.

• 원의 중심과 벽의 거리가 원의 반지름보다 작거나 같다면 원과 벽은 연결된다.

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

class Djs
{
    int cnt;
    vector<int> p;
    public:
        Djs(int _cnt){
            cnt = _cnt+10;
            p.resize(cnt+10);
            for(int i = 0; i<cnt+10; i++){
                p[i] = i;
            }
        }

        int Find(int x)
        {
            if(x == p[x]) return x;
            else return p[x] = Find(p[x]);
        }

        void Union(int x, int y)
        {
            x = Find(x);
            y = Find(y);
            if(x != y) p[x] = y;
        }
};

int n, m, k;
tuple<int, int, int> xys[1'001];

int tw, bw, lw, rw;

signed main()
{
    FASTIO;
    cin >> m >> n >> k;
    Djs djs(k);
    tw = k;
    bw = k+1;
    lw = k+2;
    rw = k+3;
    for(int i = 0; i<k; i++){
        int x, y, s;
        cin >> x >> y >> s;
        xys[i] = {x, y, s};
        
        if(x-s<=0) djs.Union(i, lw);
        if(y-s<=0) djs.Union(i, tw);
        if(x+s>=m) djs.Union(i, rw);
        if(y+s>=n) djs.Union(i, bw);
    }

    for(int i = 0; i<k; i++){
        for(int j = i+1; j<k; j++){
            auto[xi, yi, si] = xys[i];
            auto[xj, yj, sj] = xys[j];

            ll dist = 1LL*(xi-xj)*(xi-xj)+1LL*(yi-yj)*(yi-yj);
            // cout << dist <<", " << si+sj <<"\\n";
            if(dist<=1LL*(si+sj)*(si+sj)){
                djs.Union(i, j);
            } 
        }
    }

    if(djs.Find(tw) == djs.Find(lw)){
        cout << "N";
    }
    else if(djs.Find(rw) == djs.Find(bw)){
        cout << "N";
    }
    else if(djs.Find(tw) == djs.Find(bw)){
        cout << "N";
    }
    else if(djs.Find(rw) == djs.Find(lw)){
        cout << "N";
    }
    else{
        cout << "S";
    }
    
    // cout << "\\n";
    // cout << djs.Find(0) <<" " << djs.Find(1);
    
    return 0;
}