문제

출처 : https://www.algospot.com/judge/problem/read/FORTRESS

중세의 성과 요새들은 보안을 튼튼히 하면서도 더 넓은 영역을 보호하기 위해 여러 개의 성벽을 갖고 있었다고 하지요. 전세계에서 가장 편집증이 심한 영주가 지은 스트로고(Strawgoh) 요새는 이의 극치를 보여줍니다. 이 요새는 그림과 같이 커다란 원형 외벽 내에 여러 개의 원형 성벽이 겹겹이 지어진 형태로 구성되어 있는데, 어떤 성벽에도 문이 없어서 성벽을 지나가려면 사다리를 타고 성벽을 오르내려야 합니다. 요새 내에서도 한 곳에서 다른 곳으로 이동하는 데 시간이 너무 오래 걸린다는 원성이 자자해지자, 영주는 요새 내에서 왕래가 불편한 곳들을 연결하는 터널을 만들기로 했습니다. 계획을 세우기 위해 요새 내에서 서로 왕래하기 위해 가장 성벽을 많이 넘어야 하는 두 지점을 찾으려고 합니다. 예를 들어 위 그림의 경우, 별표로 표시된 두 지점 간을 이동하기 위해서는 다섯 번이나 성벽을 넘어야 하지요.

성벽들의 정보가 주어질 때 가장 성벽을 많이 넘어야 하는 두 지점 간을 이동하기 위해 몇 번이나 성벽을 넘어야 하는지 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 100) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 성벽의 수 N (1 <= N <= 100) 이 주어집니다. 그 후 N 줄에는 각 3개의 정수로 각 성벽의 위치와 크기에 대한 정보 xi , yi , ri 가 주어집니다. (0 <= xi, yi <= 1000,1 <= ri <= 1000,0 <= i<N) 이 때 i 번 성벽은 (xi, yi) 를 중심으로 하는 반지름 ri 인 원형으로 설치되어 있습니다. 편의상 모든 성벽의 두께는 0이라고 가정하며, 입력에 주어지는 성벽들은 서로 겹치거나 닿지 않습니다. 입력에 주어지는 첫 번째 성벽은 외벽이며, 외벽은 입력에 주어지는 모든 다른 성벽을 포함합니다.

출력

각 테스트 케이스마다 한 줄에 두 지점 간 이동을 위해 최대 몇 번이나 성벽을 넘어야 하는지를 출력하세요.

풀이(책 참고)

문제의 원 모양을 보면 각 원마다 포함하고 있는 하위 원들이 있으므로, 이를 트리구조로 변환하여 풀 수 있다. 맨 위의 루트에서 잎과 잎 사이의 간격 중 가장 긴 것이 답으로 볼 수 있는데, 좌표형태로 표현된 입력값을 트리구조로 변환하는 작업과 두 원간의 포함관계를 표현하는 것이 까다로웠다.

먼저, 주어진 좌표들과 반지름으로 구성된 원을 트리로 표현하는 함수를 구현한다. 이 때 중요한 것은, 각 원간의 포함관계를 확인하는 함수가 필요한데, 원과 원 사이에 다른 원이 없이 직접적으로 포함하였는지 여부만을 확인해야 한다.

class Tree {
	Vector<Tree> children;
	Tree(){
		this.children = new Vector<Tree>();
	}
}

static Tree makeTree(int root) {
		Tree t = new Tree();
		for (int i = 0; i < n; i++)
			if (isChild(root, i))
				t.children.add(makeTree(i));
		return t;
}

맨 첫번째 입력이 외벽이므로, 0번 원(성벽)이 루트 노드가 된다. makeTree함수를 통해 루트 노드의 번호를 입력받았을 때, 모든 노드를 순회하여 해당 노드와 포함여부를 체크하는 isChild함수를 통해 직접적으로 포함되었을 경우 해당 노드의 자식으로 추가하도록 구현하였다.

static int pow(int n) {
		return n * n;
}

static boolean isIn(int p, int c) {
	return R[p] > R[c] && (pow(X[c] - X[p]) + pow(Y[c] - Y[p])) < pow(R[p] - R[c]);
}

static boolean isChild(int p, int c) {
	if(!isIn(p,c))
		return false;
	for (int i = 0; i < n; i++)
		if (i != p && i != c && isIn(p, i) && isIn(i, c))
			return false;
	return true;
}

두 원간의 포함여부를 확인하는 함수 isChild를 구현하는데, 두 원의 포함여부는 각 반지름과 중심간의 거리를 통해 확인할 수 있다. 특히, 모든 노드를 검사하여 두 노드 사이에 포함된 또다른 원이 존재할 경우 직접 포함관계가 아니므로 false를 리턴하도록 한다.

static int height(Tree root) {
		Vector<Integer> heights = new Vector<Integer>();
		for (int i = 0; i < root.children.size(); i++)
			heights.add(height(root.children.get(i)));
		if(heights.isEmpty())
			return 0;
		Collections.sort(heights);
		if(heights.size()>=2)
			longest = Math.max(longest, 							2+heights.get(heights.size()-2)+heights.get(heights.size()-1));
		return heights.lastElement()+1;

}

static int solve(Tree root) {
		longest = 0;
		int h = height(root);
		return Math.max(longest, h);
}

트리 구조 구현을 마치면, 주어진 트리에서 가장 긴 경로를 탐색하여야 한다. 입력받은 노드에 대하여 해당 트리의 높이를 반환하는 함수 height를 구현하는데, 이 때 가장 긴 경로는 잎과 잎사이 길이의 최댓값 또는 전체 트리의 높이이므로, height 함수에서 잎과 잎 사이의 길이의 최댓값을 재귀적으로 찾도록 한다. 이는, 입력받은 트리에 대해 자식들의 높이 중 가장 긴 높이와, 그다음으로 긴 높이의 합을 더한 값이 되므로, 입력받은 노드의 자식들을 모아 정렬하고 해당 두 값을 찾아 최댓값을 검색하도록 구현할 수 있다. 이 때, 전체 경로는 루트 노드또한 포함하여야 하므로 각각 1씩 더하여 계산된다.