백준 1393번 : 음하철도 구구팔 [문자열/C/C++]

문제 링크 : https://www.acmicpc.net/problem/1393

1393번: 음하철도 구구팔

문제 |

최백준은 음하철도 구구팔에 탔다.

문제는 구구팔의 기장인 조교 김재홍이 반쯤 미쳐서 열차를 멈추지 않는다는 것이다. 그래서 최백준은 달리고 있는 열차에서 뛰어내려야 한다.

그런데 뛰어내릴 때 정류장 까지 거리가 너무 멀면 마이 아플 수 있다.

그래서 철도가 정류장에 가장 많이 근접했을 때 뛰어내리고자 한다.

어디서 뛰어내려야 하는가?

 

입력 |

첫째 줄에는 정류장의 위치 x y가 주어지고, 둘째 줄에는 현재 열차의 위치 X Y와 열차가 초마다 이동하는 x좌표 y좌표가 주어진다. 열차는 항상 직선으로 움직인다.

주어지는 모든 수는 -100이상, 100이하의 정수이다.

 

출력 |

최백준이 뛰어내리는 위치를 출력한다. 정답은 항상 정수이다.

#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;

float getDistance(float x1, float y1, float x2, float y2)
{
	float dist = sqrt(((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (y2 - y1)));
	return dist;
}
int checkValue(float x1, float y1, float x2, float y2, float i, float j)
{
	float a = (y2 - y1) / (x2 - x1);
	float b = -1;
	float c = a * (-1 * x1) + y1;
	if ((a * i) + (b * j) + c == 0)
		return 1;
	else
		return 0;
}
int main()
{
	float x1, x2, x3, y1, y2, y3;
	float distance;
	float min_distance = 142;
	float min_x = 0, min_y = 0;
	cin >> x3 >> y3;
	cin >> x1 >> y1 >> x2 >> y2;
	x2 = x1 + x2;
	y2 = y1 + y2;
	if (x2 - x1 == 0)
	{
		if (y2 - y1 > 0)
		{
			for (float i = y1; i < 100; i++)
			{
				distance = getDistance(x1, i, x3, y3);
				if (distance < min_distance)
				{
					min_distance = distance;
					min_x = x1;
					min_y = i;
				}
			}
		}
		else
		{
			for (float i = y1; i > -100; i--)
			{
				distance = getDistance(x1, i, x3, y3); 
				if (distance < min_distance)
				{
					min_distance = distance;
					min_x = x1;
					min_y = i;
				}
			}
		}
	}
	else if (y2 - y1 == 0)
	{
		if (x2 - x1 > 0)
		{
			for (float i = x1; i <= 100; i++)
			{
				distance = getDistance(i, y1, x3, y3);
				if (distance < min_distance)
				{
					min_distance = distance;
					min_x = i;
					min_y = y1;
				}
			}
		}
		else
		{
			for (float i = x1; i >= -100; i--)
			{
				distance = getDistance(i, y1, x3, y3); 
				if (distance < min_distance)
				{
					min_distance = distance;
					min_x = i;
					min_y = y1;
				}
			}
		}
	}
	else
	{
		float inclination = (y2 - y1) / (x2 - x1);
		if (inclination > 0) 
		{
			if (x2 - x1 < 0 && y2 - y1 < 0)
			{
				for (float i = x1; i >= -100; i--)
				{
					for (float j = y1; j >= -100; j--)
					{
						if (checkValue(x1, y1, x2, y2, i, j) == 1)
						{
							distance = getDistance(i, j, x3, y3);
							if (distance < min_distance)
							{
								min_distance = distance;
								min_x = i;
								min_y = j;				
							}
						}
					}
				}
			}
			else if (x2 - x1 > 0 && y2 - y1 > 0) 
			{
				for (float i = x1; i <= 100; i++)
				{
					for (float j = y1; j <= 100; j++)
					{
						if (checkValue(x1, y1, x2, y2, i, j) == 1)
						{
							distance = getDistance(i, j, x3, y3);
							if (distance < min_distance)
							{
								min_distance = distance;
								min_x = i;
								min_y = j;								
							}
						}
					}
				}

			}
		}
		else if (inclination < 0) 
		{
			if (x2 - x1 < 0) 
			{
				for (float i = x1; i >= -100; i--)
				{
					for (float j = y1; j >= -100; j--)
					{
						if (checkValue(x1, y1, x2, y2, i, j) == 1)
						{
							distance = getDistance(i, j, x3, y3);
							if (distance < min_distance)
							{
								min_distance = distance;
								min_x = i;
								min_y = j;								
							}
						}
					}
				}

			}
			else if (y2 - y1 < 0)
			{
				for (float i = x1; i <= 100; i++)
				{
					for (float j = y1; j <= 100; j++)
					{
						if (checkValue(x1, y1, x2, y2, i, j) == 1)
						{
							distance = getDistance(i, j, x3, y3);
							if (distance < min_distance)
							{
								min_distance = distance;
								min_x = i;
								min_y = j;								
							}
						}
					}
				}
			}
		}
	}
	cout << min_x << " " << min_y << endl;
}

무려 5시간 동안 걸쳐서 풀어낸 문제이다. 솔직히 코드 짜는건 1시간도 채 안 걸렸는데 코드를 어떻게 짤 지 설계하는 단계에서 시간을 다 잡아먹었다. 문제만 보면 길이가 얼마 안 되어서 엄청 쉬워보이는데 막상 이해하고 코드화 시키려니까 머리 터지는 문제였다.

 

처음에 문제 이해를 이상하게 해서 시간을 날려먹었다. 두 번째 줄에 주어지는 좌표값에서 처음 입력하는건 현재 위치라는 것을 알겠는데 그 다음 좌표가 무엇을 나타내는지 이해를 못했다. 그래서 백준 사이트에서 관련 질문글을 찾아보다가 이것이 증가량을 나타낸다는 것을 알았다. 첫번째 좌표가 (2, 1)이니 1초 뒤에 좌표는 (2, 4)만큼 늘어나서 (4, 5)가 되는 것이다.

 

이제 문제를 어떻게 풀어야하는지 조금 가시화되었다. 첫 번째 좌표와 두 번째 좌표를 관통하는 직선을 그어서 기차의 이동경로를 그리고 정류장의 위치에서 직선에 수선의 발을 찾아 그 좌표를 출력하면 되는 것이다. 여기서 생각해야 할 것이 직선은 직선인데 첫번째 좌표 이전의 선은 이동할 방향이 아니므로 없다고 친다. 그 이후의 이동경로 선상의 점들만 문제에 등장하는 최백준이 기차에서 뛰쳐나갈 수 있는 지점이 되는 것이다. 그리고 기차가 이동하는 방향이 어디냐에 따라 좌표 값을 검사하는 범위가 달라진다.

 

범위는 크게 3가지이다. 증가량의 좌표값에서 x가 0일 경우에는 y값에만 변동이 생긴다는 의미이다. 이러면 이동경로는 그래프 상에서 수직이 된다. 만약 y가 0일 경우에는 x값에만 변동이 생기므로 이동경로는 수평이 된다. 그렇지 않고 기울기가 있을 경우에는 각 좌표가 양의 크기로 늘어나는지, 아니면 음의 크기로 줄어드는지 알아낼 필요가 있다. 그리고 알아낸 기준으로 이동경로 상의 좌표들을 하나하나 훑어서 정류장과의 가장 거리가 가까운 좌표를 찾아내면 된다.

 

다음은 같이 스터디하신 분이 정리해주신 코드 구조이다.

 

1. 직선의 방정식이 수평인 경우

 1-1. 증가량 중 x값이 음수라면 -100 방향으로 기차가 이동하기 때문에 현재 좌표부터 -100까지 계산

 1-2. 증가량 중 x값이 양수라면 +100 방향으로 기차가 이동하기 때문에 현재 좌표부터 +100까지 계산

2. 직선의 방정식이 수직인 경우

 2-1. 증가량 중 y값이 양수라면 +100 방향으로 기차가 이동하기 때문에 현재 좌표부터 +100까지 계산

 2-2. 증가량 중 y값이 음수라면 -100 방향으로 기차가 이동하기 때문에 현재 좌표부터 -100까지 계산

3. 직선의 방정식이 기울기를 가질 경우

 3-1. 기울기가 양수인 경우

  3-1-1. 증가량이 두 값 모두 음수인 경우, -100 방향으로 간다고 생각하고 계산

  3-1-2. 증가량이 두 값 모두 양수인 경우, +100 방향으로 간다고 생각하고 계산

 3-2. 기울기가 음수인 경우

  3-2-1. x값이 음수인 경우, -100 방향으로 간다고 생각하고 계산

  3-2-2. y값이 음수인 경우, 100 방향으로 간다고 생각하고 계산

 

그리고 함수를 2개 정도 따로 만들었는데, 하나는 직선과 정류장 사이의 거리를 계산(getDistance)하는 함수이고 다른 하나는 좌표가 직선상에 있는지 검사(checkValue)하는 함수이다.