백준 1004 c - baegjun 1004 c

https://www.acmicpc.net/problem/1004

1004번: 어린 왕자

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주��

www.acmicpc.net

백준 1004 c - baegjun 1004 c
백준 1004 c - baegjun 1004 c
출처 : https://www.acmicpc.net/problem/1004

점과 원사이 관계로 푸는 문제.

출발 지점과 도착 지점이 주어진 원에 대하여 두 점이 모두 원 안쪽에 속하는지, 둘다 속하지 않은 경우 해당 원을 진입하거나 이탈 할 필요가 없습니다.

어느 한 지점만 속한 경우 반드시 진입 또는 이탈을 해야하므로 이 경우에만 1 증가 시켜주면 됩니다.

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int t;
	cin >> t;
	for (; t--;) {
		int sx, sy, dx, dy;
		int n;
		int ans = 0;
		cin >> sx >> sy >> dx >> dy >> n;
		
		for (int i = 0; i < n; i++) {
			int x, y, r;
			cin >> x >> y >> r;
			int cnt = 0;
			int dist = (sx - x) * (sx - x) + (sy - y) * (sy - y);
			if (dist <= r * r) {
				cnt += 1;
			}
			dist = (dx - x) * (dx - x) + (dy - y) * (dy - y);
			if (dist <= r * r) {
				cnt += 1;
			}
			if (cnt == 1) { // 출발 또는 도착 지점 중 한점만 원에 속함
				ans += 1;
			}

		}
		cout << ans << "\n";
	}
}

어린 왕자 🔗

🔗 전체 1004번 문제

조건 🔗

문제 🔗

어린 왕자는 소혹성 B-664에서 자신이 사랑하는 한 송이 장미를 위해 살아간다. 어느 날 장미가 위험에 빠지게 된 것을 알게 된 어린 왕자는, 장미를 구하기 위해 은하수를 따라 긴 여행을 하기 시작했다. 하지만 어린 왕자의 우주선은 그렇게 좋지 않아서 행성계 간의 이동을 최대한 피해서 여행해야 한다. 아래의 그림은 어린 왕자가 펼쳐본 은하수 지도의 일부이다.

백준 1004 c - baegjun 1004 c

빨간 실선은 어린 왕자가 출발점에서 도착점까지 도달하는데 있어서 필요한 행성계 진입/이탈 횟수를 최소화하는 경로이며, 원은 행성계의 경계를 의미한다. 이러한 경로는 여러 개 존재할 수 있지만 적어도 3번의 행성계 진입/이탈이 필요하다는 것을 알 수 있다.

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

입력 🔗

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 과 도착점 이 주어진다. 두 번째 줄에는 행성계의 개수 이 주어지며, 세 번째 줄부터 n줄에 걸쳐 행성계의 중점과 반지름 이 주어진다. 입력제한은 다음과 같다.

좌표와 반지름은 모두 정수이다.

출력 🔗

각 테스트 케이스에 대해 어린 왕자가 거쳐야 할 최소의 행성계 진입/이탈 횟수를 출력한다.

케이스 🔗

  • 입력

02
1-5 1 12 1
27
31 1 8
4-3 -1 1
52 2 2
65 5 1
7-4 5 1
812 1 1
912 1 2
10-5 1 5 1
111
120 0 2

  • 출력

풀이 🔗

1002번째 알고리즘의 내용을 응용하면 쉽게 풀 수 있는 문제인 것 같다. 실제로 별다른 레퍼런스를 찾지도 않고 풀 수 있었으니.

문제를 풀기 전에 몇 가지 집고 넘아갈 게 있다.
숫자들 때문에 입력의 한 세트를 착각하기 쉽다.

위 예제를 기준으로 설명하면, 첫 번째 숫자는 세트의 갯수. 본문에서는 2이므로, 두 세트를 테스트하므로 결과는 두 줄이 출력된다.
이후 테스트에 필요한 데이터가 출력된다.

-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 <= 행성 갯수만큼 출력됨

또한, 결과는 행성계의 진입/이탈 횟수를 통틀어서 출력하므로 굳이 진입/이탈을 구분하여 저장할 필요는 없다.

문제에서 출발점에서 도착점까지 가는데 통과해야하는 행성계(이하 원, circle)의 최소를 목적으로 두기 때문에, 반드시 통과해야하는 원만 계산하면 된다.
출발/도착점이 임의의 원 안에 포함될 경우 반드시 진입/이탈이 일어난다. 따라서, 출발/도착점을 온전히 포함하는 원의 갯수를 계산하면 진입/이탈의 횟수를 구할 수 있다.
주의할 점이 있는데, 한 원이 출발/도착점을 모두 포함할 경우 계산에서 제외시켜야 한다.
하나의 원이 출발/도착점을 전부 포함할 경우, 원 안에서 이동하기 때문에 진입/이탈이 일어나지 않기 때문.

백준 1004 c - baegjun 1004 c

원리는 간단하다. 원점과 점의 거리를 계산한다. 계산한 거리가 원의 반지름보다 짧을 경우, 해당 원은 점을 포함하는 셈이다.
이를 식으로 정리하면 아래와 같다.

변수의미
, 원점 좌표
, 원의 원점 좌표
원의 반지름

변수는 위 표와 같이 정의하고 한 원이 원점을 포함하는 식을 전개한다.

위 식을 코드로 표현하면 되는 비교적 간단한 알고리즘이다.

전체 소스 🔗

0import java.util.Scanner;
1
2/**
3 * 백준 전체 1004 문제 알고리즘 클래스
4 *
5 * @author RWB
6 * @see <a href="https://blog.itcode.dev/posts/2021/05/22/a1004">1004 풀이</a>
7 * @since 2021.04.24 Sat 02:15:31
8 */
9public class Main
10{
11 /**
12 * 메인 함수
13 *
14 * @param args: [String[]] 매개변수
15 */
16 public static void main(String[] args)
17 {
18 Scanner scanner = new Scanner(System.in);
19
20 int length = scanner.nextInt();
21 scanner.nextLine();
22
23 for (int i = 0; i < length; i++)
24 {
25 String base = scanner.nextLine();
26
27 int x_start = Integer.parseInt(base.split(" ")[0]);
28 int y_start = Integer.parseInt(base.split(" ")[1]);
29
30 int x_end = Integer.parseInt(base.split(" ")[2]);
31 int y_end = Integer.parseInt(base.split(" ")[3]);
32
33 int through = 0;
34
35 int count = scanner.nextInt();
36 scanner.nextLine();
37
38 for (int j = 0; j < count; j++)
39 {
40 String circle = scanner.nextLine();
41
42 int x = Integer.parseInt(circle.split(" ")[0]);
43 int y = Integer.parseInt(circle.split(" ")[1]);
44 int r = Integer.parseInt(circle.split(" ")[2]);
45
46 boolean hasStartContain = hasContain(x_start, y_start, x, y, r);
47 boolean hasEndContain = hasContain(x_end, y_end, x, y, r);
48
49 // 해당 행성이 출발 혹은 도착점 중 하나만을 포함할 경우
50 if (!(hasStartContain && hasEndContain) && (hasStartContain || hasEndContain))
51 {
52 through++;
53 }
54 }
55
56 System.out.println(through);
57 }
58
59 scanner.close();
60 }
61
62 /**
63 * 출발/도착점 포함 여부 반환 함수
64 *
65 * @param xo: [int] 출발/도착점의 x좌표
66 * @param yo: [int] 출발/도착점의 y좌표
67 * @param x: [int] 행성의 x좌표
68 * @param y: [int] 행성의 y좌표
69 * @param r: [int] 행성의 반지름
70 *
71 * @return [boolean] 출발/도착점 포함 여부
72 */
73 private static boolean hasContain(int xo, int yo, int x, int y, int r)
74 {
75 return Math.sqrt(Math.pow(xo - x, 2) + Math.pow(yo - y, 2)) < r;
76 }
77}

분류 🔗

  • 기하학