[LeetCode] 752. Open the Lock

https://leetcode.com/problems/open-the-lock/description/

Leetcode - Open the Lock

문제 유형 : dfs/bfs, 문자열 처리

문제 난이도 : Medium

 

문제

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

 

자물쇠에는 4개의 원형 잠금장치가 있습니다. 0~9까지 표기되어있습니다. 돌려서 값을 바꿀 수 있습니다.

9는 0으로, 0은 9로 한 번에 이동가능합니다.

이 자물쇠는 "0000"에서 시작합니다. 문자열로 표기됩니다.

 

deadends배열에 있는 숫자로 설정된다면, 그 자리에서 더 이상 진행하지 못합니다.

target이 주어지니, 0000에서 몇 번의 조작으로 target으로 맞출 수 있는지 알아내시오. 불가능하면 -1을 반환하시오.

 

풀이

그래프로 생각해보면, 

[][][][]에서 한 칸씩 위아래로 변경시켜보는 경우의 수로 탐색할 수 있다.

그러면, 현재 상태에서 총 8가지의 경우의 수로 나뉜다.

bfs를 이용하면 빨리 찾을 수 있겠다.

map에 key: 문자열, value : 회전횟수로 데이터를 저장한다.

deadend의 요소들은 미리 -1로 해놓고 탐색하면, 편하게 찾을 수 있다.

 

코드

C++

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        if(target == "0000") return 0;
        unordered_map<string, int> mp;
        for(const auto &deadend : deadends) {
            if(deadend == "0000") return -1;
            mp[deadend] = -1;
        }

        queue<string> q;
        q.push("0000");
        mp["0000"] = 0;

        while(!q.empty()) {
            string curr = q.front();
            q.pop();
            if(curr == target) break;

            for(int i = 0; i < 4; i++) {
                string newStr = curr;
                // 한 칸씩 위아래로 돌려봄
                newStr[i] = ((curr[i] - '0' + 1) % 10) + '0';

                if(mp[newStr] == 0) {
                    mp[newStr] = mp[curr] + 1;
                    q.push(newStr);
                }

                newStr = curr;
                newStr[i] = ((curr[i] - '0' + 9) % 10) + '0';
                if(mp[newStr] == 0) {
                    mp[newStr] = mp[curr] + 1;
                    q.push(newStr);
                }
            }
        }

        return mp[target] == 0 ? -1 : mp[target];
    }
};