[Baekjoon] 1002번: 터렛

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

1002번: 터렛

 

고등학생 시절 어느 한 수학 선생님께서 우리 학생들에게 이렇게 말씀을 해주신 것이 기억난다. 어쩌면 우리 고등학교에서 뿐만 아니라 전국의 학생들은 한 번쯤 들어본 말일 수도 있을 것 같다.

'수학을 잘하는 사람들은 주어진 문제를 간단하게 만들어서 푸는 것을 잘 하는 사람들이야.'

문장 자체로만 보면 정말 너무나도 당연한 명제에 따른 자명한 결론이라서 할 말이 없을 것이다. 문제를 간단하게 만들 수 있으면 당연히 간단한 문제로 푸는 게 더 쉬울 테니까... 그러나 여기서의 핵심은 '주어진 문제를 어떻게 간단하게 바꾸는가' 이다. 물론 주어진 문제와 전혀 관계 없는 동떨어진 문제를 해결하는 건 의미가 없으니, 당연스럽게도 주어진 문제와 동등한 다른 문제로 바꿔야한다는 것도 중요할 것이다.

 

위의 상황을 살짝 수학적으로 표현을 해보면, 우리는 복잡하게 서술되어 있는 주어진 문제를 논리적으로 분석하여 주어진 문제와 동치(equivalent)인 다른 더 증명하기 쉬운 명제로 이를 해석하고, 해석한 명제를 증명하면 되는 것이라고 할 수도 있겠다. 지난 포스트 중의 다리 놓기 문제와 같이, 알고 있는 개념을 활용하여 문제를 해결하는 것을 요구하는 서술형 문제의 경우에는 문제를 바로 보았을 때에는 어떻게 해결해야겠다는 생각이 바로 들지 않는다면, 이렇게 주어진 조건을 정리하고 논리적으로 분석하여 근본적으로 이 문제가 나에게 물어보는 핵심 개념이 무엇인지를 정확하게 파악하는 것이 문제 해결에 용이할 때가 많다. 참고로 블로그 주인의 부모님의 둘째 아들내미도 수학과 출신인데 이걸 잘 못해서 항상 오래 생각에 잠긴다.

 

문제에서는 유네스코(UNESCO)에 현재 우리나라 민속 놀이로서 문화유산으로 등재되기 위한 심사를 거치고 있는(당연히 농담입니다, it's just joke. 반박 질문 안 받음ㅋㅋ) 스타크래프트(Starcraft) 라는 게임에 대한 내용을 표면 상으로 제시하면서 어떠한 수학적인 개념을 우리에게 요구하고 있다.

 

---

 

문제 해결 과정

착안

스타크래프트라는 게임을 아는 사람은, (물론 터렛이 게임 내에서 지상 공격을 수행하지는 않지만) 터렛이라는 건축물에 대한 게임적/현실적 배경 지식을 통해 문제를 더 쉽게 이해할 수 있었을 수도 있다. 문제에서 제시한 조건을 정리하면 다음과 같다.

• 조건 1: 관측자 1(문제에서 조규현 분)의 좌표 및 관측자 1로부터 타겟(문제에서 류재명 분 = 마린)까지의 거리
• 조건 2: 관측자 2(문제에서 백승환 분)의 좌표 및 관측자 2로부터 타겟까지의 거리

위의 두 조건이 주어졌을 때, 타겟이 2차원 좌표 평면 상에서 존재할 수 있는 위치의 수를 계산하는 것이 우리의 목적이다.

 

수학을 조금 열심히 공부한 사람이라면 바로 캐치할 수 있을 개념 중의 하나는, 평면 위에서 고정된 한 지점(= 중심)으로부터 같은 거리에 있는 점들을 모두 모은 집합을 우리는 수학적으로 '원(circle)' 이라고 정의하여 부른다는 것이다. 따라서, 각각 조건 1과 조건 2를 만족하면서 타겟이 존재할 수 있는 위치는 (각 조건을 별도로 보면) 원의 형태로 나타낼 수 있다. 그렇기 때문에 주어진 문제는 두 조건을 동시에 만족하는 지점, 즉 각각의 조건을 만족했을 때 그려지는 두 개의 원 사이의 교점의 수를 찾는 문제로 변환할 수 있는 것이다.

 

수학에 능통한 사람은 여기까지만 생각이 진행되면 바로 이 문제를 해결할 수 있다. 그러나 본인은 대학교에서 수학을 4 년간 전공까지 했음에도 불구하고 너무 오랜만에 이런 기하학 문제를 접하여 어떻게 교점의 수를 찾을지 한참 고민했으므로, 그 과정을 기록해놓으려고 한다(... 저를 가르치신 교수님들께 머쓱하네요... 그러나 이렇게 암기가 아닌 유도를 해내는 게 수학의 본질 아니겠습니까 깔깔깔 (말은 잘하는 수학과 출신 학생임)).

 

두 원 사이의 관계에 따른 교점의 개수를 추론하는 문제는 다시 한 번 이해하기에 용이한 동치 명제로 간단하게 바꿀 수 있다. 일반적으로 생각해보면 좌표 평면 상에 두 원의 중심이 어디에 존재할 지 알 수가 없기 때문에 두 원이 모두 자유분방하게 돌아다니는 경우를 생각할 수 있다. 그러나 조금만 생각해보면 두 원의 중심이 좌표 평면 상의 어디에 있든지, 두 원의 중심을 연결한 직선을 그려보면 우리는 두 원 사이의 관계를 좀 더 간단하게 일반화할 수 있다는 것을 깨닫게 된다.

 

좌표 평면 사이의 두 원의 관계는, 두 원의 중심을 잇는 가상의 직선과 하나의 원을 고정한 뒤에 따져보는 것과 별반 다르지 않다 !

 

즉 위의 그림과 같은 상황을 살짝 수학적으로 표현해보면 주어진 문제에서 하나의 원과 두 원 사이의 중심을 잇는 축을 한 방향으로 고정시킨 뒤, 다른 나머지 원을 그 축 위에 나타내어 두 원 사이의 관계를 따지는 것이 일반성을 잃지 않는다고 할 수 있을 것이다. 따라서 우리는 오른쪽 그림에서와 같이 한 원을 0 지점에 고정시켜놓고, 다른 원의 중심을 수직선 상에 위치시켜 두 원 사이의 거리를 따져보는 것을 통해 문제를 해결할 수 있다.

 

이 다음의 단계는 솔직하게 말해서 수학적 센스가 있으면 빠르게 이해할 수 있고, 수학적 센스가 부족하면 조금 어려울 수도 있을 것 같다. 수학적 센스가 부족하면 그냥 일일이 조건문을 달아 해결하면 되고, 수학적 센스가 뛰어나면 조건문을 더 간단명료하게 짜면 되는 부분이라 크게 중요한 부분은 아니다(적어도 이 문제에 있어서는). 두 원 사이의 관계는 아래와 같이 나뉜다. 아래에서는 검정색 원을 고정시키고 회색 원이 움직인다고 가정해서 표현해보았다. 또한 두 원의 중심 사이의 거리를 \(d\), 둘 중에서 큰 원의 반지름을 \(R\), 작은 원의 반지름을 \(r\)이라고 편의상 나타내었다.(그림 편집 실력이 좋지 못한 점 양해...)

 

 

위의 조건을 예쁘게 정리해보면, 두 원 사이의 관계는 아래의 4 가지로 전부 표현이 가능함을 확인할 수 있다.

1. 교점이 무수히 많다: \(d = 0, R = r\)
2. 교점이 없다: \(d < R - r\) 또는 \(d > R + r\)
3. 교점이 1 개이다: \(d = R - r\) 또는 \(d = R + r\)
4. 교점이 2 개이다: \(R - r < d < R + r\)

결국, 주어진 문제는 두 원 사이의 거리 \(d\)가 \(R - r, R + r\)의 값보다 크거나 작거나 같은지만 비교하면 되는 문제와 동치라고 할 수 있다. 

 

구현

위 분석한 결과를 그대로 프로그래밍하여 조건문을 잘 처리해주면 쉽게 구현할 수 있다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
	int T;
	int x1, x2, y1, y2, r1, r2;

	scanf("%d", &T);
	while (T--)
	{
		scanf("%d %d %d %d %d %d", &x1, &y1, &r1, &x2, &y2, &r2);

		int dx = x2 - x1, dy = y2 - y1;
		double d = sqrt(dx * dx + dy * dy);
		double rdiff = r1 > r2 ? r1 - r2 : r2 - r1;
		double rsum = r1 + r2;

		if (!dx && !dy && r1 == r2)
			printf("-1\n");
		else
		{
			if (d < rdiff || d > rsum)
				printf("0\n");
			else if (d == rdiff || d == rsum)
				printf("1\n");
			else
				printf("2\n");
		}
	}

	return 0;
}

 

실행 결과

* 코드를 제출한 시점과 글 작성 시점이 달라, 주석 추가 등의 이유로 실행 결과의 코드 길이는 상이할 수 있음.