프로그래머스 1단계 - 키패드 누르기

https://programmers.co.kr/learn/courses/30/lessons/67256

코딩테스트 연습 - 키패드 누르기

- 문제 파악

핸드폰 숫자 패드를 왼쪽 엄지와 오른쪽 엄지로 주어진 배열 numbers 요소의 순서대로 누르려고 한다. 1,4,7은 왼쪽, 3,6,9는 오른쪽, 2,5,8,0은 가장 가까이있는 손가락으로 누르되, 두 손가락의 거리가 같다면 주어지는 hands에 따라 오른쪽 또는 왼쪽 손가락으로 누른다. 이 때 numbers 요소의 순서대로 누른 손가락을 차례대로 출력하라.

 

- 정답

BFS로 접근하여 풀었다.

그런데 그 자리에 계속 머물러 있는 경우를 생각하지 못해서 헤맸다.

BFS말고 맨해튼 거리 방법으로도 접근할 수 있어보인다. 나중에 풀어보자.

#include "bits/stdc++.h"

using namespace std;

#define X second
#define Y first

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

string answer = "";

void answer_func(pair<int, int> &lastkey, pair<int, int> key, char word)
{
    lastkey = key;
    answer.push_back(word);
}

int func(int a, pair<int, int> key, pair<int, int> lastkey, int hand) // hand : 0 right, 1 left
{
    
    if (lastkey.Y == key.Y && lastkey.X == key.X)
        return 0;
    
    int nminlim = -1;
    int nmaxlim = -1;

    int pad[4][3] = { 0, };
    
    queue<pair<int, int>> q;
    q.push(lastkey);

    if (hand)
    {
        nminlim = 0;
        nmaxlim = 1;
        if (a == 3 || a == 6 || a == 9)
            return -1;
    }
    else
    {
        nminlim = 1;
        nmaxlim = 2;
        if (a == 1 || a == 4 || a == 7)
            return -1;
    }


    while (!q.empty())
    {
        int x = q.front().X;
        int y = q.front().Y;
        

        
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx < nminlim || nx > nmaxlim) continue;
            if (ny < 0 || ny > 3) continue;
            if(pad[ny][nx]) continue;

            pad[ny][nx] = pad[y][x] + 1;

            if (ny == key.Y && nx == key.X)
                return pad[ny][nx];

            q.push({ ny,nx });
        }

    }

}



string solution(vector<int> numbers, string hand) {

    pair<int, int> lastkey_l = { 3,0 };
    pair<int, int> lastkey_r = { 3,2 };

    for (auto a : numbers)
    {
        pair<int, int> key;
        switch (a)
        {
        case 1:
            key = { 0,0 };
            break;
        case 2:
            key = { 0,1 };
            break;
        case 3:
            key = { 0,2 };
            break;
        case 4:
            key = { 1,0 };
            break;
        case 5:
            key = { 1,1 };
            break;
        case 6:
            key = { 1,2 };
            break;
        case 7:
            key = { 2,0 };
            break;
        case 8:
            key = { 2,1 };
            break;
        case 9:
            key = { 2,2 };
            break;
        case 0:
            key = { 3,1 };
            break;
        }

        int L = -1; L = func(a, key, lastkey_l, 1);
        int R = -1; R = func(a, key, lastkey_r, 0);

        if (L < R)
        {
            if (L == -1)
                answer_func(lastkey_r,key,'R');
            else    
                answer_func(lastkey_l,key,'L');   
            
        }
        else if (R < L)
        {
            if (R == -1)
                answer_func(lastkey_l,key,'L');
            else           
                answer_func(lastkey_r,key,'R'); 
        }
        else
        {
            if (hand == "right")
                answer_func(lastkey_r,key,'R');  
            else
                answer_func(lastkey_l,key,'L');
        }


    }



    return answer;
}