[C++] 키패드 누르기

[문제]

코딩테스트 연습 - 키패드 누르기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

BFS를 이용해서 문제를 풀었다.

숫자 키패드가 4 X 3으로 이루어진 그래프라고 가정하면

처음 왼쪽 손가락은 {3,0} 위치에 오른쪽 손가락은 {3,2} 위치에 있고

1,3,6을 움직이면 각각 왼쪽 손가락을 {0,0}, {1,0}, {2,0} 으로 가게 되고 3,6,9의 경우에는 오른쪽 손가락을 {0,2}, {1,2}, {2,2} 로 가게 만들었다.

문제의 핵심은 2,5,6,8에서는 현재 위치해 있는 오른쪽과 왼쪽 손가락이 각각 해당 위치까지 얼만큼 걸리는지를 파악한 후 더 가까운 손가락을 answer에 추가해 주었다.

[회고]

난이도에 비해 너무나도 어렵게 풀었던 문제.

BFS를 이용해서 문제를 풀려면 레벨2 어지간한 문제들보다 구현해야 하는 양이 많아진다.

심지어 함수화를 해서 재사용성을 제법 높였다고 생각했는데도 구현하는 양이 상당했다.

 

다 풀고 나서 다른 사람들의 코드를 보니 맨하탄 거리 계산법이라는 말이 있어서 찾아보니 단순히 [x2 - x1] + [y2 - y1] 의 거리를 계산하는 방식이다.

이걸 보고 생각이 났는데 굳이 bfs로 구하지 않고 왼쪽과 오른쪽의 현재 위치를 알고 있으니 좌표값만을 이용해서 풀었다면 코드가 절반은 줄어들었을 것이다.

[코드]

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int visited[10][10];
pair<int ,int > rSide;
pair<int, int > lSide;
string hands;

//bfs를 이용해 거리 파악하기.
int bfs(pair<int,int> goal, pair<int,int> hand){
    
    if(goal == hand)
        return -1;
    
    for(int i = 0;i<4;i++){
        for(int j = 0;j<4;j++){
            visited[i][j] = 0;
        }
    }
    
    int answer = 0;
    queue<pair<pair<int,int>,int > > q;
    q.push(make_pair(hand,0));
    int dx[4] = {0,1,0,-1};
    int dy[4] = {1,0,-1,0};

    while(q.size() > 0){
        pair<int,int> cur = q.front().first;
        int cnt = q.front().second;
        q.pop();
        for(int i = 0;i<4;i++){
            int nextX = cur.first + dx[i];
            int nextY = cur.second + dy[i];
            if(nextX == goal.first && nextY == goal.second){
                q = queue<pair<pair<int, int>, int> >();
                answer = cnt;
                break;
            }
            if(nextX >= 0 && nextX < 3 && nextY >= 0 && nextY < 3){
                if(visited[nextX][nextY] == 0){
                    visited[nextX][nextY] = 1;
                    q.push(make_pair(make_pair(nextX,nextY),cnt + 1));
                }
            }
        }
    }
    return answer;
}

//좌측과 우측 어느쪽이 더 가까운지 파악한 후 answer에 해당 결과 넣기.
string judges(pair<int,int> cur, string answer) {
    if(bfs(cur,rSide) < bfs(cur, lSide)) {
        answer += "R";
        rSide = cur;
    }
    else if(bfs(cur,rSide) > bfs(cur, lSide)) {
        answer += "L";
        lSide = cur;
    }
    else {
        answer += hands;
        if(hands == "R")
            rSide = cur;
        else
            lSide = cur;
    }
    return answer;
}

string solution(vector<int> numbers, string hand) {
    string answer = "";
    
    hands = (hand == "right") ? "R" : "L";
    lSide = {3,0};
    rSide = {3,2};
    
    for(int i = 0;i<numbers.size();i++){
        if(numbers[i] == 1 || numbers[i] == 4 || numbers[i] == 7){
            answer += "L";
            if(numbers[i] == 1)
                lSide = {0,0};
            else if(numbers[i] == 4)
                lSide = {1,0};
            else if(numbers[i] == 7)
                lSide = {2,0};
        }
        else if(numbers[i] == 3 || numbers[i] == 6 || numbers[i] == 9){
            answer += "R";
            if(numbers[i] == 3)
                rSide = {0,2};
            else if(numbers[i] == 6)
                rSide = {1,2};
            else if(numbers[i] == 9)
                rSide = {2,2};
        }
        else {
            if(numbers[i] == 2){
                answer = judges(make_pair(0,1), answer);
            }
            else if(numbers[i] == 5){
                answer = judges(make_pair(1,1), answer);
            }
            else if(numbers[i] == 8){
                answer = judges(make_pair(2,1), answer);
            }
            else if(numbers[i] == 0) {
                answer = judges(make_pair(3,1), answer);
            }
        }
    }
    
    return answer;
}