[백준] 1459번 걷기(C++)

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

 

오랜만에 PS를 해봤다. 꾸준히 해야되는데 일과 병행하는 것은 정말 쉽지 않다.

 

최소비용을 구하는 문제이다. 

 

두가지 풀이법이 생각난다. 

 

BFS 

대각선이동, 좌우이동이 가능한 BFS를 사용하면 예제는 풀릴 것이다. 그러나

X와 Y는 1,000,000,000보다 작거나 같은 음이 아닌 정수이고

라는 문구를 보고 BFS는 접어야함을 알 수 있다. 왜냐하면 BFS의 시간 복잡도는 행렬그래프에서는 O(M ^(N * N)) 이기 때문이다. (M은 가능한 방향) 즉 여기서는 좌우이동, 대각선이동까지 총 8방향이 가능하기 때문에 시간복잡도가 엄청나게 커진다.

 

Greedy

해당 문제는 좌우이동과 대각선의 비용이 다르다. 즉, 0,0 에서 1,1로 이동할 때 좌 1번, 위 1번 혹은 대각선 1번으로 이동할 수 있다.

그러므로 최소비용을 사용한다면 만약 대각선이동 비용이 대각선이 싸다면 반드시 대각선만 이용해야한다.

 

그렇다면 이것을 Greedy로 풀이할 수 있겠다.

 

의사코드를 짜보자.

 

if 대각선이동비용이 더 싸다면

-> 대각선이동을 최대한 사용

 

else 대각선이용비용이 더 비싸다면 

-> 대각선은 사용할 일이 없으므로 좌우이동만 사용한다.

 

대각선을 사용하지 않는 건 간단하다 그러나 대각선을 사용할 때 대각선을 최대한 대각선을 사용하기 위해서는 어떻게 해야할까? 

바로 주어진 좌표를 a, a 처럼 같은 값으로 이동시킨 후 a * 대각선비용을 하면 된다.

 

무슨말이냐면 4, 2로 이동할 때 2,2 까지 이동시킨 후 2 * 대각선이동비용을 한다.

그러므로 6, 2로 대각선을 최대한 이용하는 비용은

우측으로 4칸 이동시키고 대각선으로 2칸이동하는 것과 같으며

우측으로 4칸 이동하는 것도 우측 4번 혹은 대각선 2번 중 싼 값을 사용한다.

 

최종 의사코드는 다음과 같다.

if 대각선 이동이 더 싸면
 -> 목표가 6, 2 이면 4칸 우측 이동 후 2칸 대각선이동

else 대각선 이동이 더 비싸면
 -> answer = (x + Y) * 좌우비용

 

코드로 나타내면 아래와 같다.

#include <iostream>

using namespace std;

/* 대각선 비용 계산 함수 */
long long calcDiagonalExp(int x, int y, long long w, long long s) {
    /* 정사각형으로 맞추기 */
    long long exp = 0;
    
    /* 좌우 */
    if(s > w) { 
        exp = w * abs(x - y);
    } 
    /* 대각 */
    else {
        exp = s * abs(x - y);
    }

    return s * min(x, y) + exp;
}

bool checkDiagonalmove(int x, int y) {
    int originPoint = abs(x - y);

    /* 0,0 으로 옮겼을 때 홀수이면 갈 수 없음 */
    if(originPoint % 2 != 0) {
        return false;
    } else {
        return true;
    }
}

int main() {
    int x, y; 
    long long w, s;

    cin >> x >> y >> w >> s;

    long long answer = 0;

    /* 대각선이동 비용이 저렴하면 대각선만 사용함 */
    if(w * 2 > s) {
        if(checkDiagonalmove(x, y)) {
            answer = calcDiagonalExp(x, y, w, s);
        } else {
            if(x > y) {
                answer = calcDiagonalExp(x - 1, y, w, s) + w;
            } else {
                answer = calcDiagonalExp(x, y - 1, w, s) + w;
            }       
        }
    } else {
        answer = (x + y) * w;
    }

    cout << answer << "\n";
}