프로그래머스 - 숫자 타자 대회 [C++]

이 문제는 맵과 다이나믹 프로그래밍을 이용해서 풀었다.

 

이 문제를 처음에 그리디로 접근하려다가 다이나믹 프로그래밍 문제임을 알게 되었다.

왼손과 오른손 모두 똑같은 가중치로 특정 숫자에 갈 때가 문제였는데, 이 때 임의의 손을 선택하게 된다면 다음 숫자들에 대해 결과가 달라지기 때문에 그리디로는 풀 수 없다.

 

따라서 완전 탐색을 사용해야하는데, 왼손이 위치하는 숫자, 오른손이 위치하는 숫자, 현재 숫자(눌러야하는 숫자) 총 세 개의 파라미터를 통해 하나의 독립적인 상태를 만들 수 있었다. 따라서 다이나믹 프로그래밍으로 속도를 빠르게 만들 수 있어 문제를 해결할 수 있었다.

 

이 문제에서 가장 까다로웠던 것은 키패드의 위치와 숫자를 매칭하고, 최단 거리를 찾는 로직 두 개였다. 키패드의 위치와 숫자를 매칭하는 것은 맵으로 해결했으나, 숫자와 pair를 왔다갔다하면서 코드가 조금 복잡해졌다.

또한 최단 거리를 찾는 로직에 대해서는 일단 base case로 출발 숫자와 목적 숫자가 같은 경우, 직교상에 위치하는 경우, 대각선에 위치하는 경우를 빼냈다. 그리고 한 번에 갈 수 없는 경우 (거리가 2이상)에는 중간 단계로 거쳐가야 할 숫자를 정해야하는데, 가중치를 적게 하기 위해서는 (위, 오른쪽) 으로 두 번에 가는 것보다는 대각선으로 한번에 가는 것이 빠르므로 대각선을 우선적으로 잡도록 구현했다.

#include <string>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
using namespace std;

map<int, pair<int, int>> numberToCoor;
map<pair<int, int>, int> coorToNumber;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, -1, 0, 1};
int dy2[] = {-1, -1, 1, 1};
int dx2[] = {-1, 1, -1, 1};
int dp[10][10][100000];

void init() {
    numberToCoor[1] = {0, 0};
    numberToCoor[2] = {0, 1};
    numberToCoor[3] = {0, 2};
    numberToCoor[4] = {1, 0};
    numberToCoor[5] = {1, 1};
    numberToCoor[6] = {1, 2};
    numberToCoor[7] = {2, 0};
    numberToCoor[8] = {2, 1};
    numberToCoor[9] = {2, 2};
    numberToCoor[0] = {3, 1};
    coorToNumber[{0, 0}] = 1;
    coorToNumber[{0, 1}] = 2;
    coorToNumber[{0, 2}] = 3;
    coorToNumber[{1, 0}] = 4;
    coorToNumber[{1, 1}] = 5;
    coorToNumber[{1, 2}] = 6;
    coorToNumber[{2, 0}] = 7;
    coorToNumber[{2, 1}] = 8;
    coorToNumber[{2, 2}] = 9;
    coorToNumber[{3, 1}] = 0;
}

bool isSame(pair<int, int>& src, pair<int, int>& dst) {
    return (src == dst);
}

bool isOrthogonal(pair<int, int>& src, pair<int, int>& dst) {
    int y = src.first;
    int x = src.second;
    
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        if (dst.first == ny && dst.second == nx) {
            return true;
        }
    }
    return false;
}

bool isDiagonal(pair<int, int>& src, pair<int, int>& dst) {
    int y = src.first;
    int x = src.second;
    
    for (int i = 0; i < 4; i++) {
        int ny = y + dy2[i];
        int nx = x + dx2[i];
        
        if (dst.first == ny && dst.second == nx) {
            return true;
        }
    }
    return false;
}

pair<int, int> findNext(pair<int, int>& src, pair<int, int>& dst) {
    pair<int, int> nextCoor = src;
    
    int sy = src.first;
    int sx = src.second;
    int ny = dst.first;
    int nx = dst.second;
    int cost = 0;
    
    int distY = sy - ny;
    int distX = sx - nx;
    
    if (distY > 0) {    // src가 더 아래에
        if (distX > 0) {    // src가 오른쪽에
            nextCoor.first--;
            nextCoor.second--;
            cost = 3;
        } else if (distX < 0) { // src가 왼쪽에
            nextCoor.first--;
            nextCoor.second++;
            cost = 3;
        } else {    // 같음
            nextCoor.first--;
            cost = 2;
        }
    } else if (distY < 0) {     // src가 더 위에
        if (distX > 0) {    // src가 오른쪽에
            nextCoor.first++;
            nextCoor.second--;
            cost = 3;
        } else if (distX < 0) { // src가 왼쪽에
            nextCoor.first++;
            nextCoor.second++;
            cost = 3;
        } else {    // 같음
            nextCoor.first++;
            cost = 2;
        }
    } else {    // src와 dst가 같은 높이에
        if (distX > 0) {    // src가 오른쪽에
            nextCoor.second--;
            cost = 2;
        } else if (distX < 0) { // src가 왼쪽에
            nextCoor.second++;
            cost = 2;
        } else {    // 일치 (불가능)
            
        }
    }
    
    int number = coorToNumber[nextCoor];
    return {number, cost};
}

int calculate(int src, int dst) {
    pair<int, int>& srcCoor = numberToCoor[src];
    pair<int, int>& dstCoor = numberToCoor[dst];
    
    if (isSame(srcCoor, dstCoor)) {
        return 1;
    }
    if (isOrthogonal(srcCoor, dstCoor)) {
        return 2;
    }
    if (isDiagonal(srcCoor, dstCoor)) {
        return 3;
    }
    
    pair<int, int> nextInfo = findNext(srcCoor, dstCoor);
    int nextNumber = nextInfo.first;
    int cost = nextInfo.second;
    
    return calculate(nextNumber, dst) + cost;
}

int solve(int left, int right, int index, string& numbers) {
    // base case
    if (index == numbers.size()) {
        return 0;
    }
    if (dp[left][right][index] != 0) {
        return dp[left][right][index];
    }
    
    int presentNumber = numbers[index] - '0';
    
    // calculate cost
    int leftCost = calculate(left, presentNumber);
    int rightCost = calculate(right, presentNumber);
    
    // 둘 중 하나라도 가중치가 1이면(제자리면) 무조건 걔를 눌러야함
    if (leftCost == 1) {
        return dp[left][right][index] = solve(presentNumber, right, index + 1, numbers) + leftCost;
    } else if (rightCost == 1) {
        return dp[left][right][index] = solve(left, presentNumber, index + 1, numbers) + rightCost;
    } else {    // 그게 아니라면, 둘다 실행해봐야함
        int leftMove = solve(presentNumber, right, index + 1, numbers) + leftCost;
        int rightMove = solve(left, presentNumber, index + 1, numbers) + rightCost;
        
        return dp[left][right][index] = min(leftMove, rightMove);
    }
}

int solution(string numbers) {
    init();
    int answer = solve(4, 6, 0, numbers);
    
    return answer;
}