[BaekJoon] 1004 어린 왕자

1.  문제 링크

2.  문제

요약

• 어린 왕자가 서로 경계가 맞닿지 않고 교차하지 않는 여러 행성계들을 지나서 행성계 경계에 걸쳐지지 않는 출발 지점부터 행성계 경계에 걸쳐지지 않는 도착 지점까지 이동을 하는데, 이 때 행성계들의 진입/이탈 횟수를 최소로 하여 이동합니다. 이 최소 진입/이탈 횟수를 구하는 문제입니다.
• 입력
• 첫 번째 줄에는 테스트 케이스의 개수가 주어집니다.
• 테스트 케이스에서 첫 번째 줄에는 출발 지점의 x,y 좌표와 도착 지점의 x,y 좌표가 주어집니다.
• 테스트 케이스에서 두 번째 줄에는 행성계의 개수가 주어집니다.
• 그 다음 줄부터는 행성계의 중점의 x,y 좌표와 반지름이 주어집니다.
• 출력: 시작 지점에서 도착 지점까지 갈 때의 최소 행성계 진입/이탈 횟수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public boolean isInPlan(int x, int y, int plan_x, int plan_y, int radius) {
		boolean inPlan = false;
		double distance = Math.sqrt((Math.pow(x - plan_x, 2)) + (Math.pow(y - plan_y, 2)));
		if(distance < radius) {
			inPlan = true;
		}
		return inPlan;
	}
	
	public int calIOCount(int[] start, int[] end, int[] x, int[] y, int[] radius) {
		int count = 0;
		for(int i = 0; i < x.length; i++) {
			if(isInPlan(start[0], start[1], x[i], y[i], radius[i]) && isInPlan(end[0], end[1], x[i], y[i], radius[i])) {
				continue;
			} else {
				if(isInPlan(start[0], start[1], x[i], y[i], radius[i])) {
					count++;
				}
				if(isInPlan(end[0], end[1], x[i], y[i], radius[i])) {
					count++;
				}
			}
		}
		return count;
	}
	
	public ArrayList<Integer> getIOCount(int num, ArrayList<String> se, ArrayList<ArrayList<String>> plans) {
		ArrayList<Integer> count = new ArrayList<Integer>();
		for(int i = 0; i < num; i++) {
			StringTokenizer st = new StringTokenizer(se.get(i));
			int[] start = new int[2];
			int[] end = new int[2];
			start[0] = Integer.parseInt(st.nextToken());
			start[1] = Integer.parseInt(st.nextToken());
			end[0] = Integer.parseInt(st.nextToken());
			end[1] = Integer.parseInt(st.nextToken());
			ArrayList<String> plan = plans.get(i);
			int[] x = new int[plan.size()];
			int[] y = new int[plan.size()];
			int[] radius = new int[plan.size()];
			for(int j = 0; j < plan.size(); j++) {
				st = new StringTokenizer(plan.get(j));
				x[j] = Integer.parseInt(st.nextToken());
				y[j] = Integer.parseInt(st.nextToken());
				radius[j] = Integer.parseInt(st.nextToken());
			}
			count.add(calIOCount(start, end, x, y, radius));
		}
		return count;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		ArrayList<String> se = new ArrayList<String>();
		ArrayList<ArrayList<String>> plans = new ArrayList<ArrayList<String>>();
		for(int i = 0; i < num; i++) {
			se.add(br.readLine());
			int plan_num = Integer.parseInt(br.readLine());
			ArrayList<String> plan = new ArrayList<String>();
			for(int j = 0; j < plan_num; j++) {
				plan.add(br.readLine());
			}
			plans.add(plan);
		}
		br.close();
		Main m = new Main();
		ArrayList<Integer> count = m.getIOCount(num, se, plans);
		for(int i = 0; i < count.size(); i++) {
			bw.write(count.get(i) + "\n");
		}
		bw.flush();
		bw.close();
	}
}

4.  접근

• 문제의 조건에서 각 행성계들은 서로 맞닿지 않고 교차하지 않는다고 하였기 때문에 각 행성계들 사이로 지나갈 수 있으므로 최소의 행성계의 진입/이탈 횟수는 출발 지점을 감싸고 있는 행성계의 개수와 도착 지점을 감싸고 있는 행성계의 개수를 합친 수가 될 것입니다.
• 출발 지점과 도착 지점을 감싸고 있는 행성계들은 출발 지점에서 나갈 때, 도착 지점으로 들어갈 때 불가피하게 지나야만 하는 행성계들이지만 다른 행성계들은 위에서 말씀드렸듯이 행성계 사이를 지나갈 수 있기 때문입니다.
• 출발 지점이나 도착 지점을 감싸는 행성계들의 개수를 구할 때는 행성계의 반지름과 행성계 중심에서 출발 지점 혹은 도착 지점까지의 거리를 이용하면 구할 수 있습니다.
• 행성계의 반지름보다 행성계 중심에서 출발 지점 혹은 도착 지점까지의 거리가 짧다면 해당 행성계 안에 존재하는 것이고 그렇지 않다면 밖에 존재하는 것입니다. 이 두 가지로 나눌 수 있는 이유는 출발 지점 혹은 도착 지점이 행성계 경계에 걸쳐지지 않기 때문입니다.
• 이 방법을 통해 출발 혹은 도착 지점이 행성계 내부에 있는지 알아내서 이들이 내부에 존재하는 행성계의 개수를 더하면 되는데 이 때, 두 지점 모두 같은 행성계 내부에 존재한다면 이 때는 해당 행성계의 진입/이탈이 없으므로 해당 행성계는 개수로 계산하지 않습니다.
• 이러한 방식으로 구한 횟수가 최소 행성계 진입/이탈 횟수가 됩니다.