요새 풀이
- 문제(알고스팟): https://algospot.com/judge/problem/read/FORTRESS
- 제한시간: 1초
문제에서 주의할 점
- x, y 좌표의 max 값이 1000이다. 따라서 1000 x 1000개의 좌표가 존재한다.
- 모든 좌표 <-> 좌표 의 선을 연결.
- 해당 선이 몇개의 성벽을 넘는지로 계산하는 형태는 좌표가 너무 많아서 시간 초과.
- 성벽 max값은 100개, 문제 max값은 100개
- 즉 모든 좌표로 문제를 해결하는게 아니라 성벽으로 문제를 해결해야 한다.
문제에서 주어진 힌트
- 첫번째 입력값은 외곽 성벽이다.
- 즉 모든 성벽은 첫번째 성벽의 자손이다.
- 모든 성벽의 두깨는 0 이다.
- 선이 겹쳐서 2개의 성벽을 넘는걸 1개의 성벽으로 계산하는 경우는 없다.
- 모든 입력값은 겹치거나 닿지 않는다.
- 교집합 형태의 모양이 절대 생기지 않는다.
- 성벽의 특징
- 성벽은 다른 성벽의 자손이 된다.
- 성벽은 공통 부모를 둔 같은 레벨의 성벽이 된다.
- 성벽의 특징에서 트리 구조로 이를 표현 할 수 있음을 알 수 있다.
- 성벽의 중심점 (대표 좌표)는 이미 있음
- 두 개의 성벽을 가지고, 두 정점(중심점)간의 거리와 반지름을 이용하면, 성벽의 포함 관계를 알 수 있음.
문제에서 원하는 답은 성벽을 가장 많이 건너는 값 이다. 따라서 아래와 같은 풀이를 생각 할 수 있다.
첫째, 성벽을 트리 구조로 표현한다.
둘째, 자손이 없는 성벽(가장 깊은 곳에 있는 성벽)들을 추려낸다.
셋째, 자손이 없는 성벽간의 path (그래프로보면 간선) 을 계산한다.
셋째 방법의 경우, 트리에서 두 Leaf 노드의 depth계산 하고, 공통부모이면 depth 공통부모의 depth를 빼주면 된다.
풀이코드
Java로 풀이함
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
class F_WallChecker {
F_Wall walls[];
public F_WallChecker(F_Wall[] walls) {
super();
this.walls = walls;
Arrays.sort(walls, new Comparator<F_Wall>() {
@Override
public int compare(F_Wall o1, F_Wall o2) {
return Integer.compare(o2.r, o1.r);
}
});
}
public boolean checkWallInsidePoint(int x, int y, F_Wall wall) {
// check first wall inside point
// a^2 + b^2 = c^2
int xDist = Math.abs(x - wall.x);
int yDist = Math.abs(y - wall.y);
int r = wall.r;
if (Math.pow(r, 2) > Math.pow(xDist, 2) + Math.pow(yDist, 2)) {
return true;
}
return false;
}
public boolean checkWallInsidePoint(F_Wall child, F_Wall parent) {
if (child.r >= parent.r) {
return false;
}
return checkWallInsidePoint(child.x, child.y, parent);
}
public void createTree() {
for (int i = 0; i < walls.length; i++) { // 100
F_Wall wall = walls[i];
for (int j = 0; j < walls.length; j++) { // 100
if (i == j) {
continue;
}
F_Wall otherWall = walls[j];
if (checkWallInsidePoint(wall, otherWall)) {
wall.parentId = otherWall.id;
wall.depth++;
otherWall.allChildIds.add(wall.id);
}
}
} // 10000
}
public F_Wall getWallById(int id) {
for (int i = 0; i < walls.length; i++) {
if (walls[i].id == id) {
return walls[i];
}
}
return null;
}
public F_Wall getSameParentWall(F_Wall a, F_Wall b) {
F_Wall sa = a, sb = b;
if (sa.depth > sb.depth) {
// up same level
for (int i = 0; i < Math.abs(a.depth - b.depth); i++) {
sa = getWallById(sa.parentId);
}
} else if (sa.depth < sb.depth) {
// up same level
for (int i = 0; i < Math.abs(a.depth - b.depth); i++) {
sb = getWallById(sb.parentId);
}
}
if (sa.parentId == sb.parentId) {
return getWallById(sa.parentId);
}
return getSameParentWall(getWallById(sa.parentId), getWallById(sb.parentId));
}
public int getMaxDepth(ArrayList<F_Wall> leafList) {
F_Wall wall = leafList.get(0);
int max = 0;
if (leafList.size() == 1) {
return wall.depth;
}
for (int i = 1; i < leafList.size(); i++) {
F_Wall otherWall = leafList.get(i);
F_Wall sameParentWall = getSameParentWall(wall, otherWall);
// (자기 dep - 공통부모 dep) + (다른놈 dep - 공통부모 dep) == 성벽
int newMax = (wall.depth - sameParentWall.depth) + (otherWall.depth - sameParentWall.depth);
max = Math.max(max, newMax);
}
return max;
}
public ArrayList<F_Wall> getChildWall(F_Wall wall) {
ArrayList<F_Wall> wallList = new ArrayList<F_Wall>();
for (int i = 0; i < walls.length; i++) { // 100
if (walls[i].parentId == wall.id) {
wallList.add(walls[i]);
}
}
return wallList;
}
public ArrayList<F_Wall> getLeafWall() {
ArrayList<F_Wall> wallList = new ArrayList<F_Wall>();
for (int i = 0; i < walls.length; i++) {
if (walls[i].allChildIds.size() == 0) {
wallList.add(walls[i]);
}
}
return wallList;
}
public int check() {
createTree();
// get all leaf wall
ArrayList<F_Wall> leafWallList = getLeafWall();
// sort by depth
leafWallList.sort(new Comparator<F_Wall>() {
@Override
public int compare(F_Wall o1, F_Wall o2) {
return Integer.compare(o2.depth, o1.depth);
}
});
// calc depth
return getMaxDepth(leafWallList);
}
}
class F_Wall {
int x, y, r;
int parentId = -1;
int id;
int depth = 0;
ArrayList<Integer> allChildIds = new ArrayList<Integer>();
public F_Wall(int x, int y, int r) {
super();
this.x = x;
this.y = y;
this.r = r;
}
@Override
public String toString() {
return "id: (" + this.id + "), pid:(" + this.parentId + "), depth:(" + depth + "), child:"
+ allChildIds.toString()
+ "\n";
}
}
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int C = Integer.parseInt(br.readLine());
for (int tc = 0; tc < C; tc++) {
// create wall
int N = Integer.parseInt(br.readLine());
F_Wall walls[] = new F_Wall[N];
for (int wn = 0; wn < N; wn++) {
String wallStr = br.readLine();
StringTokenizer st = new StringTokenizer(wallStr);
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int r = Integer.parseInt(st.nextToken());
F_Wall wall = new F_Wall(x, y, r);
wall.id = wn;
walls[wn] = wall;
}
// get answer
F_WallChecker wc = new F_WallChecker(walls);
bw.write(Integer.toString(wc.check()));
bw.newLine();
}
br.close();
bw.flush();
bw.close();
}
}