4 - 1. Disjoint-set 예제 (10216번: Count Circle Groups)

백준 10216번(Count Circle Groups)

10216번: Count Circle Groups

 

SW Maestro 10기가 끝났습니다.

최종 결과 나올 때까지 오지게 문제만 풀려다가, 서로소 집합 관련 문제를 올리려 했던 게.. 기억나서 부리나케 왔습니다. ㅎㅎ

 

따로 분류는 안되어있지만, 저는 서로소 집합으로 해결한 문제를 가져왔습니다.

 

 

 

'배열로 처리해서 바로 인접한 그룹의 개수를 센다.'라고 생각하실지도 모르겠지만,

 

시간 복잡도만 생각해보아도.. 살짝 위험해 보입니다.

또한 인접하거나 겹친 부분을 제대로 인식하기 어렵겠죠..

 

따라서 일반 2차원 좌표상에 존재한다 생각하고 문제를 접근하면 될 것 같습니다.

그리고 또한 대놓고 진영의 모양이 원이라고 알려줌으로써 문제 푸는 게 좀 더 수월해졌네요.^___^

 

이제 문제를 풀어보면 될 것 같은데, 그전에 이해를 돕기 위해 그림으로 그려보겠습니다.

(문제에 주어진 예제 입력을 예시로 그려보겠습니다.)

 

 

 

그림을 그리면 이렇게 첫 번째 예제는 두 진영이 붙어있어 1개의 그룹으로,

2번째 예제는 앞의 두 진영은 한 그룹이지만 마지막 진영은 거리가 멀어 통신이 불가하므로 총 2개의 그룹임을 볼 수 있습니다.

 

풀이는 상당히 간단합니다.

1. 입력을 받으면서 각 진영마다 idx도 함께 저장해줍니다.
2. N <= 3,000 이므로 중첩 반복문을 통해 위에서 각 진영별로 idx를 통해 접근합니다.
3. 접근한 진영_i와 진영_j의 x, y 값을 가져와 다른 함수를 선언해 Euclidean distance('Edist'라 하겠습니다.)를 구하고
4. 이를 각 진영의 반지름 합을 구하여 (radius_i + radius_j) >= Edist 인 경우 참을 반환하게 합니다.
5. 따라서 참의 값이 반환된다면 merge 메서드를 통해 묶어 하나의 집합으로 만듭니다. (반복)
6. 이후 반복문을 통해 전체 집합 크기를 갖는 배열의 개수를 반환하면 됩니다.
7. 집합의 크기를 갖는 배열은 다른 배열과 다르게 배열 내에 음수의 값을 갖고 있으니 찾는데 어려움은 없겠네요. :)

 

다음으로, 이에 대한 코드를 하나씩 보여드리도록 하겠습니다.

for(int i = 0; i < N; i++) {
	StringTokenizer st = new StringTokenizer(br.readLine());
    
    int x = Integer.parseInt(st.nextToken());
    int y = Integer.parseInt(st.nextToken());
    int r = Integer.parseInt(st.nextToken());
    
	coor[i] = new Coordinate(x, y, r);
}

-> 1. Coordinate 이너 클래스 생성하여 좌표와 반지름 값 저장, 해당 클래스 배열을 통한 index 저장.

 

for(int camp1 = 0; camp1 < N; camp1++) {
	for(int camp2 = camp1 + 1; camp2 < N; camp2++) {					
		// 3, 4, 5에 해당되는 코드
	}
}

-> 2. 중첩 반복문을 통한 각 진영의 중심 좌표(x, y) 접근

 

private static boolean compRangeWithDistance(Coordinate c1, Coordinate c2) {
	int distPow = (c1.x - c2.x) * (c1.x - c2.x) + (c1.y - c2.y) * (c1.y - c2.y);
	int radar = (c1.range + c2.range) * (c1.range + c2.range);
		
	return radar >= distPow;
}

-> 3, 4 distPow(Edist)와 radar(radius_i + radius_j)를 비교해 값 반환

 

for(int camp1 = 0; camp1 < N; camp1++) {
	for(int camp2 = camp1 + 1; camp2 < N; camp2++) {					
		if(compRangeWithDistance(coor[camp1], coor[camp2])) {
			merge(camp1, camp2);
		}
	}
}

-> 3, 4, 5를 종합한, 거리 계산을 통한 집합 생성 코드

 

 

최종 결과 코드

10216.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Boj10216 {
	private static int[] parent;
	private static final String NEW_LINE = "\n";
	
	private static class Coordinate{
		int x;
		int y;
		int range;
		
		public Coordinate(int x, int y, int range) {
			this.x = x;
			this.y = y;
			this.range = range;
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		while(T-- > 0) {
			int N = Integer.parseInt(br.readLine());
			Coordinate[] coor = new Coordinate[N];
			parent = new int[N];
			
			Arrays.fill(parent, -1);
			
			for(int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
                
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                int r = Integer.parseInt(st.nextToken());
                
				coor[i] = new Coordinate(x, y, r);
			}
			
			for(int camp1 = 0; camp1 < N; camp1++) {
				for(int camp2 = camp1 + 1; camp2 < N; camp2++) {					
					if(compRangeWithDistance(coor[camp1], coor[camp2])) {
						merge(camp1, camp2);
					}
				}
			}
			
			int count = 0;
			
			for(int i = 0; i < parent.length; i++) {
				if(parent[i] < 0) count++;
			}
			
			sb.append(count).append(NEW_LINE);
		}
	
		System.out.println(sb);
	}
	
	private static int find(int x) {
		if(parent[x] < 0) return x;
		else return parent[x] = find(parent[x]);
	}
	
	private static void merge(int x, int y) {
		x = find(x);
		y = find(y);
		
		if(x == y) return;
		
		if(parent[x] < parent[y]) {
			parent[x] += parent[y];
			parent[y] = x;
		}
		else {
			parent[y] += parent[x];
			parent[x] = y;
		}
	}
	
	private static boolean compRangeWithDistance(Coordinate c1, Coordinate c2) {
		int distPow = (c1.x - c2.x) * (c1.x - c2.x) + (c1.y - c2.y) * (c1.y - c2.y);
		int radar = (c1.range + c2.range) * (c1.range + c2.range);
		
		return radar >= distPow;
	}
}

(코드 인덴테이션이 왜..자꾸....휴)

 

원래는 좀 더 새로운 느낌의 서로소 집합 문제를 써볼까 했는데요.. 다음에 기회가 되면 해보겠습니다. ㅎㅎ

물론 제가 서로소 집합 문제 중 어려운 문제들을 많이 풀지 못한 이유도 있습니다... ^___^;

 

제출 결과

 

이 문제의 시간 복잡도는 제가 코드를 구성한 대로라면 O(N^2 * log∂(N)) 정도 나오겠네요. 맞..겠죠...?

(종종.. 서로소 집합은 조금 애매하고 헷갈리곤 하네요..ㅎㅎ)

네, 여기 까집니다.

 

질문이나 틀린 부분 있으면 댓글 달아주세요!

빠르게 답변이나 보완하도록 하겠습니다. 감사합니다.