[알고리즘]word Ladder, sliding-puzzle

[seroak]

❗️Todo

• [x] word Ladder
• [x] Sliding-puzzle

ETC

기타사항

[seroak]

bfs

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        graph = defaultdict(list)
        wordList.append(beginWord)
        for i in range(len(wordList)):
            for j in range(i+1, len(wordList)):
                flag = 0
                for k in range(len(beginWord)):
                    if wordList[i][k] != wordList[j][k]:
                        flag += 1
                if flag == 1:
                    graph[wordList[i]].append(wordList[j])
                    graph[wordList[j]].append(wordList[i])
        queue = deque()
        queue.append((beginWord, 1))
        vis = defaultdict(bool)
        while queue:
            word, number = queue.popleft()
            if word == endWord:

                return number
            for i in graph[word]:
                if i in vis:
                    continue
                vis[i] = True
                queue.append((i, number+1))
        else:
            return 0

[seroak]

dfs

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        answer = [sys.maxsize]
        def dfs(beginWord, endWord, wordList, vis, num):
            if beginWord == endWord:
                answer[0] = min(num, answer[0])
                return
            for i in range(len(wordList)):
                tmp = 0
                if vis[i] is True:
                    continue
                for j in range(len(wordList[i])):
                    if beginWord[j] != wordList[i][j]:
                        tmp += 1
                if tmp == 1:
                    # 방문 처리
                    vis[i] = True
                    dfs(wordList[i], endWord, wordList, vis, num+1)
                    vis[i] = False

        vis = [False for _ in range(len(wordList))]
        dfs(beginWord,endWord, wordList, vis, 1)
        if answer[0] == sys.maxsize:

            return 0
        else:

            return answer[0]