[알고리즘] 13번째 알고리즘

[SongGwanSeok]

📝 Description

무엇을?

• https://leetcode.com/problems/word-ladder/description/
• https://leetcode.com/problems/sliding-puzzle/description/

왜?

• (ex 사용자를 인증하기 위해)

❗️Todo

• [ ]
• [ ]
• [ ]

ETC

기타사항

[SongGwanSeok]

https://leetcode.com/problems/word-ladder/description/ Time Limit Exceeded

class Solution {
public:
    int wordSize;

    int findMinDepth(string nowWord, string endWord, vector<string>& wordList, vector<bool>& visited, int depth){
        depth++;
        if(nowWord == endWord){
            return depth;
        }
        int minDepth = 9999;
        int nowIdx = find(wordList.begin(), wordList.end(),nowWord) - wordList.begin();
        visited[nowIdx] = true;

        for(int i = 0; i < wordList.size(); i++){
            string word = wordList[i];
            if(word == nowWord || visited[i]) continue;
            int diffCnt = 0;
            for (int j = 0; j < wordSize; ++j) {
                if(nowWord[j] != word[j]){
                    diffCnt++;
                }
            }
            if(diffCnt == 1){
                int result = findMinDepth(word, endWord, wordList, visited, depth);
                minDepth = min(result, minDepth);
            }
        }
        visited[nowIdx] = false;
        return minDepth;
    }

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        vector<bool> visited(wordList.size(), false);
        wordSize = beginWord.size();

        if(find(wordList.begin(), wordList.end(), beginWord) == wordList.end() &&
        find(wordList.begin(), wordList.end(), endWord) == wordList.end()){
            return 0;
        }

        int result = findMinDepth(beginWord, endWord, wordList, visited, 0);

        return (result == 9999 ? 0 : result);

    }
};

[SongGwanSeok]

https://leetcode.com/problems/word-ladder/description/ 성공은 했으나 효율이 떨어짐...

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        vector<bool> visited(wordList.size(), false);
        int wordSize = beginWord.size();
        int result = 0;

        if(find(wordList.begin(), wordList.end(), endWord) == wordList.end()){
            return 0;
        }

        deque<pair<string, int>> dq;
        dq.push_back({beginWord, 0});

        while(!dq.empty()){
            pair<string, int> p = dq.front();
            string nowWord = p.first;
            int nowDepth = p.second;
            dq.pop_front();

            if(nowWord == endWord) {
                result = nowDepth + 1;
                break;
            }

            for(int i = 0; i < wordList.size(); i++){
                string word = wordList[i];
                if(word == nowWord || visited[i]) continue;
                int diffCnt = 0;
                for (int j = 0; j < wordSize; ++j) {
                    if(nowWord[j] != word[j]){
                        diffCnt++;
                    }
                }
                if(diffCnt == 1){
                    visited[i] = true;
                    dq.push_back({word, nowDepth + 1});
                }
            }
        }

        return result;
    }
};

[SongGwanSeok]

https://leetcode.com/problems/sliding-puzzle/description/

class Solution {
public:

    pair<int, int> findZero(vector<vector<int>> & board){
        pair<int, int> now;
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 3; ++j) {
                if(board[i][j] == 0){
                    now.first = i;
                    now.second = j;
                }
            }
        }
        return now;
    }

    bool isCorrect(vector<vector<int>> & board){
        return board[0][0] == 1 && board[0][1] == 2 && board[0][2] == 3
            && board[1][0] == 4 && board[1][1] == 5 && board[1][2] == 0;
    }

    int go(vector<vector<int>> & board){

        vector<int> dx = {-1, 0, 1, 0};
        vector<int> dy = {0, 1, 0, -1};

        int result = -1;
        set<vector<vector<int>>> sv;

        queue<pair<vector<vector<int>>, int>> q;
        q.push({board, 0});
        sv.insert(board);
        vector<vector<int>> nowBoard;
        vector<vector<int>> nextBoard;

        while(!q.empty()){
            auto p = q.front();
            nowBoard = p.first;
            int nowDepth = p.second;
            pair<int, int> now = findZero(nowBoard);

            q.pop();
            if(isCorrect(nowBoard)) {
                result = nowDepth;
                break;
            }

            for (int i = 0; i < 4; ++i) {
                pair<int, int> next = {now.first + dx[i], now.second + dy[i]};

                if(next.first < 0 || next.first > 1 || next.second < 0 || next.second > 2) continue;

                nextBoard = nowBoard;
                swap(nextBoard[now.first][now.second], nextBoard[next.first][next.second]);
                if(sv.find(nextBoard) != sv.end()) continue;

                q.push({nextBoard, nowDepth+1});
                sv.insert(nextBoard);
            }
        }
        return result;
    }

    int slidingPuzzle(vector<vector<int>>& board) {
        return go(board);
    }
};