[알고리즘문제] 개미 길 찾기 (상자위의 개미)

'상자 위의 개미' 문제

Question!
가로, 세로, 높이가 각각 a, b, c인 직육면체 모양의 상자가 있다. 이 상자의 표면에는 개미 두 마리가 있다. 개미 한 마리가 다른 개미가 있는 위치로 이동하려고 한다. 당신이 할 일은 이 개미에게 가장 빠른 길을 찾아서 알려주는 것이다. 개미는 상자 속으로 들어갈 수 없고, 또 바닥에 닿아있는 면으로는 이동할 수 없다.

개미의 위치를 말하기 위해서 이 상자가 다음과 같이 x,y,z-공간에 있다고 가정한다. 박스의 한 꼭지점의 좌표는 (0,0,0)이고 이 꼭지점과 가장 먼 꼭지점의 좌표는 (a,b,c)이다. 즉, 박스의 꼭지점의 좌표는 다음과 같다: (0,0,0), (a,0,0), (a,b,0), (0,b,0), (0,0,c), (a,0,c), (a,b,c), (0,b,c).
바닥에 닿아있는 면의 점들은 0<x<a, 0<y<b, z=0인 (x,y,z)들이다.

[입력 형식]

입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에 상자의 가로, 세로, 높이가 실수로 주어진다. 둘째 줄에 개미의 현재 위치의 좌표가 주어지고, 셋째 줄에 개미의 최종 위치가 주어진다. 개미의 위치는 x 좌표, y 좌표, z좌표 순서로 주어진다.

[출력 형식]

출력 파일의 이름은 OUTPUT.TX이다. 첫째 줄에 최단 경로의 길이를 출력한다.

[입력과 출력의 예]

INPUT.TXT
2.0 3.0 4.0
1.0 0.0 3.0
1.0 3.0 3.0

OUTPUT.TXT
5.0

Answer!

직육면체 도형을 펼쳐서 평면으로 만든 뒤, 피타고라스 식을 이용하여 거리를 구하는 방식을 적용.

단계1. 먼저 출발점과 끝점을 가지고, 각각의 점이 어느 평면에 속해있는지 알아내기.

(임의로 바닥 평면을 제외한 나머지 5개의 평면을 PL_1, PL_2 .. 등으로 정의하여 문제를 품)

단계2. 아래 세가지 경우로 나누어 해결
 * 첫 번째: 출발점과 끝점이 같은 평면 위에 있는 경우
 * 두 번째: 출발점과 끝점이 속한 평면이 서로 인접해 있는 경우
 * 세번째는 출발점과 끝점이 속한 평면이 서로 떨어져 있는 경우

위의 3가지 경우로 모든 경우를 분류할 수 있음.

1) 첫번째 경우

 두 점이 같은 평면위에 있으므로 간단하게 피타고라스의 정리를 이용하여 거리를 구함. 이 계산의 결과가 최단 거리.

2) 두번째 경우

 출발점과 끝점이 속한 평면이 서로 인접해 있는 경우인데, 이 경우의 최단거리는 두가지가 있을 수 있음.

 점들이 속한 두 평면만을 거쳐 가는 최단 직선이 있을 수 있고, 두 평면 외에 그 사이에 포함된 다른 평면, 즉 세 평면을 거쳐 가는 최단 직선이 있을 수 있음. 이렇게 가능한 두가지 경우를 모두 구해서 작은 거리 값을 택함.

3) 세번째 경우

 출발점과 끝점이 속한 평면이 서로 떨어져 있는 경우로, 세가지로 나누어 계산함.

 실제 출발점과 끝점이 각각 떨어져 있는 다른 평면에 있는 경우는 두가지 경우가 있음.

   - 직육면체를 정면에서 보았을 때, 앞면과 뒷면인 경우, 그리고 양쪽 측면에 있는 경우.

 이러한 경우, 세가지 경로를 생각해 볼 수 있음. (단, 직육면체를 평면도로 폈다고 가정하고 계산)

 예를 들어 앞면과 뒷면에 두 점이 있다고 할 때, 가능한 직선 거리는

   -> 좌측면을 거쳐가는 경우,

   -> 우측면을 거쳐가는 경우,

   -> 위쪽면을 거쳐가는 경우,

이렇게 세가지 경우로 나눌 수 있음. 이를 모두 구해서 가장 작은 거리 값을 택함.

프로그램 시간 복잡도 : O(상수)

소스 코드 일부

#include <stdio.h>
#include <conio.h>
#include <math.h>

#define PL_1 1 // 평면을 나타내는 값
#define PL_2 2
#define PL_3 3
#define PL_4 4
#define PL_5 10

double box[4] = {0, }, start[3], end[3]; // 상자 크기 (배열이 4로 잡힌것은 아래에 함수에 인자를 넘길 때, 계산을 간편하게 하기 위해서 사용, 크게 중요하지 않음), 시작점, 도착점

void InputFile(); // 파일 입력
void OutputFile(double distance); // 파일 출력
int GetPlane(double point[]); // 인자로 들어간 점이 어느 평면위에 있는지 알아낸다.
double GetDistance1(int sPlane, int ePlane); // 두 점이 같은 평면 또는 인접한 평면에 있을 때, 최단 거리를 구한다.
double GetDistance2(int sPlane, int ePlane); // 두 점이 속한 평면이 떨어져 있을 때, 최단 거리를 구한다.
double CalculateDistance(int x1, int x2, int xb, int y1); // 두 점사이의 거리를 구한다. 여기서 x, y는 공간상의 좌표가 아닌 평면으로 변환된 x, y 좌표
double CalculateDistance(int x1, int x2, int x3, int x4, int y1); // CalcuateDistance의 3개의 함수는 모두 비슷한 함수로 각 상황에 맞는 거리를 구하며, 이중에서 최적의 거리값이 결과값이다.
double CalculateDistance(int x1, int x2, int x3, int x4, int y1, int y2, int y3, int y4);

void main()
{
    int sPlane, ePlane; // 점이 속한 평면을 저장
    double distance; // 최단 거리 값을 저장

InputFile(); // 파일로 부터 데이터 얻기

sPlane = GetPlane(start); // 시작점이 속한 평면을 얻는다.
ePlane = GetPlane(end); // 도착점(끝점)이 속한 평면을 얻는다.

if(sPlane == ePlane) // 시작점과 끝점이 같은 평면위에 있다면
    distance = sqrt(pow(start[0] - end[0], 2) + pow(start[1] - end[1], 2) + pow(start[2] - end[2], 2)); // 피타고라스 정리
else if(abs(sPlane - ePlane) == 1 || abs(sPlane - ePlane) > 5) // 시작점과 끝점이 있는 평면이 인접해 있다면
    distance = GetDistance1(sPlane, ePlane); // 거리 구하는 함수 1
else if(abs(sPlane - ePlane) == 2) // 시작점과 끝점이 있는 평면이 떨어져 있다면
    distance = GetDistance2(sPlane, ePlane); // 거리 구하는 함수 2

OutputFile(distance);

}

소스 및 실행 파일 내려 받기

ants_on_box_source.zip