알고리즘 - 두 박스 문제

개발이 전공이 아닌 친구에게서 질문 받은 백준 알고리즘 문제입니다.

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

해당 문제는 다음과 같습니다.

위 사진과 같은 두 박스의 충돌 상태를 나타내는 문제입니다.

해당 문제는 저에게는 상당히 익숙한 문제였으며 알고리즘 적인 난이도 또한 높지 않은 문제입니다.

다만 취업을 준비하는 사람으로써 이러한 문제 방식에 익숙해질 필요가 있고 

이 문제를 해결하는 과정에서 주의 깊게 보지 않으면 놓칠 수 있는 부분이 있었어서 그 부분들을 공유 하려고 합니다.

 

해당 문제의 입력 값은 다음과 같습니다.

이 형태는 이 전에 자주 다뤘던 AABB 방식과 동일합니다.

위 사항은 제한 조건과 점수 배점에 대한 항목입니다.

서브태스크를 통해 문제풀이의 방향성을 쉽게 잡을 수 있습니다.

 

서브태스크 1번에 따라 POINT 와 LINE 인 케이스만 생각 해 보겠습니다.

이전에 Dynamic AABB tree를 기억하신다면 그것보다 훨씬 단순합니다.

사고의 편리함을 위해 가상의 통합 AABB를 그려봅시다.

각 AABB의 x,y 길이의 합이 전체 AABB x,y 값과 정확하게 같다면 두 사각형은 한 점에서 만나고 있습니다.

어느 하나가 합보다 작다면 선에서 만나고 있다는 뜻입니다.

 

이 두 조건을 통해 서브태스크 1인 POINT와 LINE 을 구분하는 것은 해결 되었습니다.

두번째 조건은 좌푯값의 제한입니다.

길이의 합과 비교를 하기에 좌푯값이 음수가 아닌 양수로만 제한 되는 것은 문제의 난이도를 낮춰 줍니다.

해당 조건에 따라 int 자료형을 사용해도 되지만 부차적인 조건은 범위가 더 넓기에 long long 자료형을

사용해 주겠습니다.

 

이 부분이 제가 문제 해결중 간과한 부분이었습니다.

사실 정수의 자료를 int 형 이외에 잘 사용하지 않았기에 해당 조건을 간과했고 그 부분에서 오류가 발생했습니다.

 

서브태스크 3를 따라서 FACE 와 NULL 도 체크하겠습니다.

크게 다르지 않습니다.

각 AABB의 x,y 길이의 합이 전체 AABB x,y 값보다 크다면 FACE 상태이고

작다면 NULL 상태입니다.

 

여기서 문제를 더 신경 쓴다면 한 AABB의 x,y 가 다른 한 AABB의 x,y 범위 안에 있는 지를 추가로

체크해 주어서 내부에 있는지 아니면 단순한 FACE 상태인지 체크하여 추가적인 조건을 만들 수 있습니다.

 

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <math.h>

using namespace std;

struct point
{
	long double x, y;
};

class box
{
public:

	long long x1, y1, x2, y2;
	long double width;
	long double height;
	point center;

	void SetBox()
	{
		width = abs(x2 - x1);
		height = abs(y2 - y1);
		center.x = x1 + width / 2;
		center.y = y1 + height / 2;
	}
};

void CheckCollision(box A, box B)
{
	if ((A.width + B.width) / 2 > abs(A.center.x - B.center.x) && (A.height + B.height) / 2 > abs(A.center.y - B.center.y))
	{
		cout << "FACE";
	}
	else if ((A.width + B.width) / 2 == abs(A.center.x - B.center.x) || (A.height + B.height) / 2 == abs(A.center.y - B.center.y))
	{
		if ((A.width + B.width) / 2 == abs(A.center.x - B.center.x) && (A.height + B.height) / 2 == abs(A.center.y - B.center.y))
		{
			cout << "POINT";
		}
		else if ((A.width + B.width) / 2 > abs(A.center.x - B.center.x) || (A.height + B.height) / 2 > abs(A.center.y - B.center.y))
		{
			cout << "LINE";
		}
		else
		{
			cout << "NULL";
		}
	}
	else
	{
		cout << "NULL";
	}
}

int main()
{
	box boxA, boxB;
	scanf("%lld %lld %lld %lld", &boxA.x1, &boxA.y1, &boxA.x2, &boxA.y2);
	scanf("%lld %lld %lld %lld", &boxB.x1, &boxB.y1, &boxB.x2, &boxB.y2);

	boxA.SetBox();
	boxB.SetBox();
	CheckCollision(boxA, boxB);

	return 0;
}

 

해당 문제의 코드는 위와 같습니다.

 

내용 자체는 단순하지만 어떤 조건을 먼저 체크해 주어야 하는지

조건 값의 범위가 어떠한지 주의 해야 할 부분이 있습니다.

처음 코딩 테스트를 수행 할 시에 마주할 수 있는 문제 이기에 쉬운 문제이더라도 시도해 보는 것을 추천 드립니다.