[백준] 1004 어린왕자

안녕하세요.

BOJ 1004 어린왕자를 풀어봤습니다.

 

문제 분석

은하수 지도

 

 

은하수 지도, 출발점, 도착점이 주어졌을 때 어린 왕자에게 필요한 최소의 행성계 진입/이탈 횟수를 구하는 프로그램을 작성해 보자.(행성계의 경계가 맞닿거나 서로 교차하는 경우는 없다고 가정한다.또한, 출발점이나 도착점이 행성계 경계에 걸쳐진 경우 역시 입력으로 주어지지 않는다.)

 => 최대한 원의 경계를 관통하지 않으면서 출발점에서 도착점으로 이동한다.

 

풀이 방법

행성이 하나만 있다고 가정했을 때 출발점과 도착점의 경우의 수는 다음과 같다.

1) 행성을 한 번도 통과하지 않고 갈 수 있다.

2) 도착점에 가기 위해선 반드시 행성을 한 번 진입해야 한다.

3) 1번과 마찬가지로 행성을 한 번도 통과하지 않고 갈 수 있다.

4) 도착점에 가기 위해선 반드시 행성을 한 번 이탈해야 한다.

 

이를 단순하게 봤을 때, 원안에 하나의 점(출발점 혹은 도착점)이 들어가있다면 반드시 진입(혹은 이탈)을 해야함을 의미한다.

 

그렇다면, 출발점 혹은 도착점이 원 안에 있다는 것은 어떻게 알 수 있을까?

바로, 원의 방정식을 이용하는 것이다. 

x와 y값에 해당 점을 대입했을 때 식을 만족하면 해당 점이 원안쪽에 있는 것이다.

 

다음 테스트 케이스를 통해 예시를 들어보겠다.

-5 1 12 1
7
1 1 8 
-3 -1 1
2 2 2
5 5 1
-4 5 1
12 1 1
12 1 2

• 원1 - 중심: (1,1) / 반지름: 8
  • 시작점 < 64 (이탈)
  • 끝점 > 64
• 원2 - 중심: (-3,-1) / 반지름: 1
  • 시작점 > 1
  • 끝점 > 1

• 원3 - 중심: (2,2) / 반지름: 2
  • 시작점 > 4
  • 끝점 > 4

• 원4 - 중심: (5,5) / 반지름: 1
  • 시작점 > 1
  • 끝점 > 1

• 원5 - 중심: (-4,5) / 반지름: 1
  • 시작점 > 1
  • 끝점 > 1

• 원6 - 중심: (12,1) / 반지름: 1
  • 시작점 > 1
  • 끝점 < 1 (진입)

• 원7 - 중심: (12,1) / 반지름: 2
  • 시작점 > 4
  • 끝점 < 4 (진입)

=> 총 진입/이탈 횟수는 3번이 된다.

 

코드

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

public class BOJ_1004_어린왕자 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int t = 0; t < T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int sx = Integer.parseInt(st.nextToken());
			int sy = Integer.parseInt(st.nextToken());
			int ex = Integer.parseInt(st.nextToken());
			int ey = Integer.parseInt(st.nextToken());

			int n = Integer.parseInt(br.readLine());
			int count = 0;
			for (int i = 0; i < n; i++) {
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				int r = Integer.parseInt(st.nextToken());

				if (include(sx, sy, x, y, r)^include(ex, ey, x, y, r)) {
					count++;
				}
			}
			sb.append(count).append("\n");
		}
		System.out.print(sb);
	}

	static boolean include(int gx, int gy, int x, int y, int r) {
		return Math.pow(gx - x, 2) + Math.pow(gy - y, 2) < Math.pow(r, 2);
	}
}