[프로그래머스 lvl1] 키패드누르기 풀이

해설

모든 정점 쌍 간의 최단 거리를 구하는 플로이드 알고리즘을 이용하여 모든 키에서 키까지의 거리를 구한다.

이후 조건 분기문을 통해 L과 R을 ret에 더해준다.

 

전체 코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <climits>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <sstream>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second
#define INF 1000
#define STAR 10
#define SHARP 11

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};


void Floyd(vector<vector<int>>& keypad, vector<vector<int>>& dist) {
    
    // 아무 노드도 거치지 않았을 때 인접한 노드끼리의 거리 셋팅
    for (int i=0; i<12; i++) dist[i][i] = 0;
    for (int i=0; i<4; i++) {
        for (int j=0; j<3; j++) {
            for (int k=0; k<4; k++) {
                int nx = i+dx[k];
                int ny = j+dy[k];
                if (nx < 0 || nx >= 4 || ny < 0 || ny >= 3) continue;
                dist[keypad[i][j]][keypad[nx][ny]] = 1;
            }
        }
    }
    
    // 다른 노드를 거쳐갔을 때의 최단 거리 고려, 최솟값 갱신
    for (int k=0; k<12; k++) {
        for (int i=0; i<12; i++) {
            for (int j=0; j<12; j++)
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
        }
    }
}


string solution(vector<int> numbers, string hand) {
    
    vector<vector<int>> keypad = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}, {10, 0, 11}};
    vector<vector<int>> dist(12, vector<int>(12, INF));
    
    Floyd(keypad, dist);
    
    string ret = "";
    int left = STAR, right = SHARP;
    for (auto x : numbers) {

        // 1, 4, 7을 입력해야 하는 경우
        if (x == 1 || x == 4 || x == 7) {
            ret += "L";
            left = x;
            continue;
        }

        // 3, 6, 9를 입력해야 하는 경우
        if (x == 3 || x == 6 || x == 9) {
            ret += "R";
            right = x;
            continue;
        }

        // 입력해야 하는 숫자 x까지의 거리가 왼손, 오른손 모두 동일할 때
        // 왼손잡이인 경우
        if (dist[left][x] == dist[right][x] && hand == "left") {
            ret += "L";
            left = x;
            continue;
        }

        // 오른손 잡이인 경우
        if (dist[left][x] == dist[right][x] && hand == "right") {
            ret += "R";
            right = x;
            continue;
        }

        // x까지의 거리가 왼손이 더 가까울 때
        if (dist[left][x] < dist[right][x]) {
            ret += "L";
            left = x;
            continue;
        }

        // x까지의 거리가 오른손이 더 가까울 때
        ret += "R";
        right = x;
    }

    return ret;
}