[프로그래머스] 조이스틱 C++ 풀이 및 해설

https://school.programmers.co.kr/learn/courses/30/lessons/42860#qna

프로그래머스

풀이 방법

현재 문자를 위, 아래로 움직여 최소로 만드는 방법은

• forward : A에서 B, B에서 C 방향으로 정방향으로 하나씩 이동하는 횟수
• backward : A에서 Z, Z에서 Y 방향으로 하나씩 이동하는 횟수

중에서 최솟값을 사용하면 된다.

 

최소로 좌, 우로 이동하는 방법은 DFS를 통해 구현 했다.

이때 좌, 우로 이동할때 방향을 2번 이상 트는것은 효율적이지 않아 최솟값이 나올 수 없으므로

visit 배열을 통해 현재 인덱스 문자의 방문 횟수를 카운트한다.

이때 3이상이라면 2번이상 방향을 틀어 방문한 경우이므로 이 경우는 가지치기(return)를 해준다.

 

전체 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// 최소로 알파벳 이동하는 방법
int minCnt(char cur, char target) {
    int forward = abs(cur - target); // 첫번째 위치 이용하지 않고 이동
    int backward = (cur - 'A' + 1) + ('Z' - target); // 첫번째 위치를 이용해서 이동
    return min(forward, backward);
}

// (인덱스, 현재 비용, 현재 문자열, 목표 문자열, 방문 횟수, answer)
void dfs(int i, int cost, string cur, string name, int visit[20], int* answer) {
    
    // 어떤 문자 위치를 3번 이상 방문하는것은 최소가 될 수 없음(방향을 두번 이상 틀면 비효율)
    if(visit[i]>2)
        return;
    
    // 위아래 이동 최소 비용 더함
    cost += minCnt(cur[i], name[i]);
    // 문자 변경
    cur[i] = name[i];
    
    if(cur == name) {
        *answer = min(*answer, cost);
        return;
    }

    if(i==0) {
        //문자 끝으로 이동
        visit[name.size()-1]++;
        dfs(name.size()-1, cost+1, cur, name, visit, answer);
        visit[name.size()-1]--;
        
        // 다음 위치로 이동
        visit[i+1]++;
        dfs(i+1, cost+1, cur, name, visit, answer);
        visit[i+1]--;
    } else if (i==name.size()-1) {
        // 첫 위치로 이동
        visit[0]++;
        dfs(0, cost+1, cur, name, visit, answer);
        visit[0]--;
        
        // 왼쪽으로 이동
        visit[i-1]++;
        dfs(i-1, cost+1, cur, name, visit, answer);
        visit[i-1]--;
    } else {
        //오른쪽 위치로 이동
        visit[i+1]++;
        dfs(i+1, cost+1, cur, name, visit, answer);
        visit[i+1]--;
        
        //왼쪽 위치로 이동
        visit[i-1]++;
        dfs(i-1, cost+1, cur, name, visit, answer);
        visit[i-1]--;
    }
    
}

int solution(string name) {
    int answer = 987654321;
    int visit[20]; // i번째 위치 방문 횟수
    fill(visit, &visit[20], 0);
    
    // 현재 문자열 상태
    string cur = "";
    for(int i=0; i<name.size(); i++)
        cur += "A";
    
    // 0번째 위치 방문 횟수 1 상태로 시작
    visit[0] = 1;
    dfs(0, 0, cur, name, visit, &answer);
    
    return answer;
}