[LeetCode] 514. Freedom Trail

https://leetcode.com/problems/freedom-trail/description/

leetcode - Freedom Trail

문제 유형 : 재귀 / dfs / 다이나믹 프로그래밍

문제 난이도 : Hard

 

문제

In the video game Fallout 4, the quest "Road to Freedom" requires players to reach a metal dial called the "Freedom Trail Ring" and use the dial to spell a specific keyword to open the door.

Given a string ring that represents the code engraved on the outer ring and another string key that represents the keyword that needs to be spelled, return the minimum number of steps to spell all the characters in the keyword.

Initially, the first character of the ring is aligned at the "12:00" direction. You should spell all the characters in key one by one by rotating ring clockwise or anticlockwise to make each character of the string key aligned at the "12:00" direction and then by pressing the center button.

At the stage of rotating the ring to spell the key character key[i]:

1. You can rotate the ring clockwise or anticlockwise by one place, which counts as one step. The final purpose of the rotation is to align one of ring's characters at the "12:00" direction, where this character must equal key[i].
2. If the character key[i] has been aligned at the "12:00" direction, press the center button to spell, which also counts as one step. After the pressing, you could begin to spell the next character in the key (next stage). Otherwise, you have finished all the spelling.

 

비디오 게임 폴아웃 4에서 "자유의 길" 퀘스트는 플레이어들에게 "프리덤 트레일 링"이라는 금속 다이얼로 특정 키워드를 입력해 문을 열게 합니다.

 

다이얼을 나타내는 문자열 ring이 있고, key문자열이 주어집니다. key문자열을 입력해야 합니다. 최소 동작 횟수를 반환하시오.

ring의 첫 글자가 12시 방향에 있고, 시계방향순으로 둥글게 ring의 글자들이 나열되어있습니다.

12시방향에 있는 글자를 입력할 수 있습니다.

 

 

당신은 시계방향 또는 반시계방향으로 돌릴 수 있고, 한 칸에 1회 동작으로 간주합니다.

버튼을 눌러 입력할 수 있습니다. 한 칸에 1회 동작으로 간주합니다.

 

풀이

모든 경우의 수를 봐야 하지만, 시간 최적화를 위해 dp가 필요하다.

dp[문자열의 인덱스][이전 다이얼인덱스] = 최소 횟수로 dp테이블을 만든다.

추가로, 각 문자들이 어느 인덱스에 있는지 알아야한다. 그리고 시계방향이 빠른지 반시계방향이 빠른지 알 수 있을 것이다.

map의 자료구조에서 key를 문자, value를 문자가 있는 회전판 내의 인덱스들로 설정한다.

 

재귀적으로 다음을 수행한다:

1. 인덱스가 key의 길이보다 크거자 같아지면, 0을 반환한다.

2. dp에 값이 있으면, dp값을 반환한다.

3. 이번에 넣을 문자로 이동하기 위해, 지난 인덱스에서 이번 문자의 인덱스까지의 최소 거리를 위해서 모든 경우의 수를 계산한다.

    그렇게 dp[idx][pos]에 현재 이동값 + 다음 이동값을 더한 값 + 1을 저장시킨다.

    다음 이동값은 재귀를 통해서 구한다.

4. 반환해준다.

 

코드

C++

class Solution {
private:
    int n,m;
    string key;
    unordered_map<int, vector<int>> mp; // charNo. -> idxes;
    vector<vector<int>> dp;
public:
    int solve(int idx, int pos) {
        if(idx >= m) {
            return 0;
        }
        if(dp[idx][pos] != -1) return dp[idx][pos];

        auto next = mp[key[idx] - 'a'];
        int res = 1e9;
        for(int i = 0; i < next.size(); i++) {
            int diff = abs(next[i] - pos);
            int curr_step = min(diff, n - diff);
            int next_step = solve(idx+1, next[i]);
            res = min(res, curr_step + next_step);
        }
        
        dp[idx][pos] = res + 1;
        return dp[idx][pos];
    }

    int findRotateSteps(string ring, string key) {
        n = ring.size();
        m = key.size();
        this -> key = key;
        dp = vector<vector<int>>(m, vector<int>(n, -1));
        for(int i = 0; i < n; i++) {
            mp[ring[i] - 'a'].push_back(i);
        }

        int ans = solve(0, 0);
        return ans;
    }
};