10216 - Count Circle Groups

개인적으로 재미있게 풀었다. 알고스팟 남극기지 문제처럼 좌표평면과 범위가 있어서 엄청 어려워보였다. (주의. 남극기지와는 다른 문제이다!)

시간 제한이 8초인건 나중에 봤고, N이 3,000 이하이길래 충분하다고 생각하고 코딩을 시작했다.

아이디어는 이랬다. (사실 문제에서 말한 그대로 하는거라 아이디어랄 것도 없다.)

아군의 통신 영역이 서로 닿거나 겹친다면 통신 가능하고, 통신이 가능한 부대끼리는 하나의 그룹처럼 이동한다. 여기서 그룹의 개수를 헤아리는 문제인데, 그렇다면 진영을 하나의 노드로 본다면, "몇 개의 그래프가 존재하는가"로 문제를 바꿔 생각할 수 있다.

정점 $A_i$ 에서 $A_j$ 로 통신 가능하다면 이동하도록 인접 리스트를 만든다. ( $O(N^2)$ )
각 정점에서 연결된 모든 정점을 방문하고 개수를 센다. (여기서 하나의 그래프를 발견) . 방문하지 않은 나머지 정점을 확인한다. ( $O(N^2)$ )

그래프를 세는 부분을 코드로 표현하면 아래와 같다.

bool dfs(vector<int> adj[], int pos){
    if(visit[pos]) return false;
    visit[pos] = true;
    for(int i=0; i<adj[pos].size(); ++i)
        dfs(adj, adj[pos][i]);
    return true;
}

memset(visit, false, sizeof(visit));
int count=0;
for(i=0; i<N; ++i){
    count += dfs(adj, i);
}
printf("%d\n", count);

지금 생각해보니 분리집합(Disjoint-set) 으로 했어도 괜찮았을것 같다.


전체 코드

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

typedef long long lld;

struct spot {
    int y, x, d;
};

int dist(spot a, spot b){
    return (b.x-a.x)*(b.x-a.x) + (b.y-a.y)*(b.y-a.y);
}

bool isConnected(spot a, spot b){
    return (a.d+b.d)*(a.d+b.d) >= dist(a, b);
}

bool visit[3001];

bool dfs(vector<int> adj[], int pos){
    if(visit[pos]) return false;
    visit[pos] = true;
    for(int i=0; i<adj[pos].size(); ++i)
        dfs(adj, adj[pos][i]);
    return true;
}

int main(){
    int T, i, j, k;
    scanf("%d", &T);
    while(T--){
        int N, x, y, r;
        scanf("%d", &N);
        spot s[3001];
        for(i=0; i<N; ++i){
            scanf("%d %d %d", &x, &y, &r);
            s[i] = {x, y, r};
        }
        
        vector<int> adj[N];   // i번째 진영과 연결되는 다른 진영
        for(i=0; i<N; ++i){
            for(j=0; j<N; ++j){
                if(i == j) continue;
                if( isConnected(s[i], s[j]) ){
                    adj[i].push_back(j);
                }
            }
        }
        
        memset(visit, false, sizeof(visit));
        int count=0;
        for(i=0; i<N; ++i){
            count += dfs(adj, i);
        }
        printf("%d\n", count);
    }
    return 0;
}