3349. 최솟값으로 이동하기(D4)

문제 링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWDTN0cKr1oDFAWD

간선을 지나는 비용은 1로 동일하다. 이 때, 여러 개의 중간 지점을 순서대로 지나는 경로의 최솟값을 구하는 문제이다.

우선, 대각선의 길을 제외하고 보자. 모든 간선의 비용이 1이므로 최솟값은 x값의 차이 + y값의 차이 이다. 이 상황을 Case 1이라고 한다.

이제 남은 부분은 대각선이 추가되는 경우이다. Case 1에서 대각선을 추가해보면 아래와 같다.

위 상황에서 대각선을 이용해서 비용을 줄일 수 있는 경우는 어떤 경우가 있을까?

1. x와 y의 값이 +1 +1인 경우 ( 둘 다 증가하는 경우 )

2. x와 y의 값이 -1 -1인 경우 ( 둘 다 감소하는 경우 )

위 두 가지 상황에서는 대각선을 이용하는 것이 비용을 줄일 수 있다. 예를 들면, 그림에서 (2,1)에서 (3,3)으로 이동한다고 할 때 (2,1), (3,2) 사이의 대각선 혹은 (2,2), (3,3) 사이의 대각선을 이용한다면 비용을 줄일 수 있다. 그리고 둘 중 하나의 대각선을 이용했다면 (3,2)에서 대각선을 다시 이용하기 위해 (2,2)로 가는 것보다 가로 세로 길을 따라 (3,3)으로 바로 가는 것이 더 비용을 줄일 수 있다.

그렇다면 대각선을 몇번 이용해야 하는지를 어떻게 구할 수 있을까?

1) 시작점과 끝 점 사이에 이동해야 하는 좌표값을 구한다.

2) x와 y 모두 양의 방향 혹은 모두 음의 방향일 경우에는 이동해야 하는 x좌표와 이동해야 하는 y좌표의 절대값을 비교하여 더 작은 값을 비용에 더한다.

     => 두 가지 모두 양의 방향 혹은 음의 방향이라면 대각선을 이용할 수 있는 경우이다.

     => 모두 양의 방향으로 이동할 수도 있고 음의 방향으로도 이동할 수 있기 때문에 절대값을 이용한다.

     => 절대값 중 작은 값을 이용하는 이유는 대각선을 이용하여 x 혹은 y 둘 중 한가지가 목표치에 도달했다는              뜻이다.

3) 대각선으로 이동하고 남은 거리만큼의 비용을 더한다.

만약, x와 y의 이동해야 하는 좌표값의 부호가 다르다면 대각선을 이용하지 않는 것이 최솟값이다 ! (대각선을 이용하면 오히려 비용이 증가함)

- 소스코드 -

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int main() {
    int T;
    cin >> T;
    for (int test_case = 1; test_case <= T; test_case++) {
        int W, H, N;
        //W : col, H : row, N : 중간 지점 개수
        cin >> W >> H >> N;
        
        int sub_row[1000] = { 0 }, sub_col[1000] = { 0 };
        
        for (int i = 0; i < N; i++) {
            scanf("%d %d", &sub_row[i], &sub_col[i]);
        }
 
        int cur_row = sub_row[0], cur_col = sub_col[0];
        int cost = 0;
 
        for (int i = 0; i < N; i++) {
            int row_dist = sub_row[i] - cur_row;
            int col_dist = sub_col[i] - cur_col;
            if (row_dist*col_dist > 0) {
                cost += min(abs(row_dist), abs(col_dist));
                abs(row_dist) > abs(col_dist) ? cost += abs(row_dist) - abs(col_dist) : cost += abs(col_dist) - abs(row_dist);
            }
            else {
                cost += abs(row_dist) + abs(col_dist);
            }
            cur_row = sub_row[i];
            cur_col = sub_col[i];
        }
        printf("#%d %d\n", test_case, cost);
    }
    return 0;
}