프로그래머스 - 조이스틱

프로그래머스 - 조이스틱

처음에 단순 구현문제인줄 알고 손가는데로 풀고 제출했다가 자꾸 케이스가 몇개 틀려서 다시 생각해보니 DFS 문제였다.

핵심은 좌로 움직일지 우로 움직일지 Greedy하게 파악하는 것으로는 답을 못 낸다는 것인데 예를 들어

1. "ABAAAABABA"

• 해당 케이스의 답은 9이다.

2. "ABABAAAABA"

• 해당 케이스의 답은 10이다.

두 케이스 모두 0번 Index의 A부터 시작해서 바로 오른쪽 B를 선택하는게 Greedy하게는 옳아 보이는데, 사실 아래 것은 바로 왼쪽으로 움직여서 8번째에 있는 B부터 선택하고, 그 다음 오른쪽으로 다시 움직여서 1, 3번째에 있는 B를 선택하는게 가장 짧은 거리이다.
즉, 각 위치에서 Greedy하게 가장 짧게 움직일 수 있는 쪽으로 움직이는 것으로는 답을 도출하지 못한다.

그렇기 때문에 각 위치마다 왼쪽 오른쪽으로 움직일지를 DFS를 통해서 모든 경우를 탐색해줘야 한다.

위 케이스 같은 경우에는 A를 제외한 알파벳이 총 3개가 존재하기 때문에
"왼왼왼", "왼왼오", "왼오왼", "오왼왼", "왼오오", "오왼오", "오오왼", "오오오" 로 총 8개의 경우에 대해서 구한 뒤 그 중 가장 작은 값을 답으로 해주면 된다.

코드는 아래와 같다.

#include <string>
#include <vector>

using namespace std;

int count = 0;
int check[21];
int answer = 1 << 12;
void dfs(string name, int current, int dir, int cnt, int len) 
{
    int amount = min(name[current] - 'A', 26 - (name[current] - 'A'));
    check[current] = 0;
    if(cnt == count) {
        answer = min(answer, len + amount);
        return;
    }
    
    if(dir == 0) {
        int left_move = 1;
        while(1) {
            if(check[(current - left_move + name.size()) % name.size()] == 1)
                break;
            left_move++;
        }
        current = (current - left_move + name.size()) % name.size();
        
        dfs(name, current, 0, cnt + 1, len + left_move + amount);
        check[current] = 1;
        
        dfs(name, current, 1, cnt + 1, len + left_move + amount);
        check[current] = 1;
    } else {
        int right_move = 1;
        while(1) {
            if(check[(current + right_move) % name.size()] == 1)
                break;
            right_move++;
        }
        current = (current + right_move) % name.size();
        
        dfs(name, current, 0, cnt + 1, len + right_move + amount);
        check[current] = 1;
        
        dfs(name, current, 1, cnt + 1, len + right_move + amount);
        check[current] = 1;
    }
}
int solution(string name) {
    for(int i=0;i<name.size();i++) {
        if(name[i] != 'A') {
            check[i] = 1;
            count++;
        }
    }
        
    if(!count)
        return 0;
    
    int cnt = name[0] == 'A' ? 0 : 1;
    int len = 0;
    dfs(name, 0, 0, cnt, len);
    dfs(name, 0, 1, cnt, len);
    
    return answer;
}