static int src[2]; //y, x
static int dst[2]; //y, x
static int solution(void)
{
scanf("%d %d %d %d", &src[1], &src[0], &dst[1], &dst[0]);
int dy = src[0] < dst[0] ? dst[0] - src[0] : src[0] - dst[0];
int dx = src[1] < dst[1] ? dst[1] - src[1] : src[1] - dst[1];
if (dy == dx)
return dy * 2;
int min = dy < dx ? dy : dx;
int max = dy > dx ? dy : dx;
int diff = max - min;
if (diff % 2)
return max * 2 - 1;
else
return max * 2;
}일단 문제를 보면 bfs로 푸는 방식이 가장 먼저 생각난다.
그래서 실제로 그렇게 작성을 해봤으나, 결과는 메모리도 많이 잡아먹고 타임아웃도 발생했다.
하지만 처음 했던 방식에서는 목적지로 가는 경로도 체크하는 방식이어서 큐에 확인해볼 경로를 넣는 조건을 몇가지 추가 해보았다. 원래 시작점에서 도착지까지의 거리보다 멀어지면 해당 경로는 폐기하는 방식으로 말이다.
하지만 역시 결과는 실패였다.
그 뒤에 나온 풀이가 위와 같고 이는 사실 간단했다.
x축 상에서 이동에 필요한 거리와 y축 상에서 필요한 이동거리만 알면 된다.
(0, 0) -> (2,2) 일 때
X축으로는 2만큼 움직여야 하고, Y축으로 역시 2만큼 움직여야 한다.
→ ↑ → ↑ 이렇게 되는 것이다.
그리고 이런 경우는 dy와 dx가 같은 경우고, dy + dx 만큼 움직여야 한다.
(0, 0) -> (1, 3) 일 때
dy = 1, dx = 3 이다.
→ ↑ → ?→ ?
?에 각각 ↑, ↓ 를 채워야 상쇄가 되어 목적지에 도달 할 수 있다. 그래서 dx * 2 만큼 움직여야 한다.
(0, 0) -> (1, 4) 일 때
dy = 1, dx = 4 이다.
→ ↑ → ?→ ?→ "?"
마지막 ?는 채울 필요가 없다. 그래서 dx * 2 - 1 만큼 움직여야 되는 것이다.