Algorithm/Programmer/DFS,BFS/level 3/単語変換(Python使用)

5327 ワード
アルゴリズム問題 programmers テキストリンク

📖 質問する



📝 解法


  • リストwordsにtarget単語がないと変換できないため、return 0

  • BFSアルゴリズムを使用します.<-これは、beginからtargetへと「最小」段階に移行するためである.(BFSを使用する場合、最初にtargetが発生するステップは最小のステップであるが、DFSの場合、より高いステップ数が必要となる.)
    隣接するノードは、アルファベットの異なる単語が1つしかありません.
    2-1. リストwordsを巡回する過程で、現在の単語とアルファベットの異なる単語のみが検索されます.(関数difference_cntの戻り値が1の単語)
    2-2. 現在の単語とアルファベットのみが他の単語が以前にアクセスしたことのないノードである場合、次のアクセスするノードが存在するキュー(q)に格納されます.
    2-3. 現在の単語がtargetである場合、現在のdepthは最小レベルであるため、変数answerに挿入され、while文は逃走する

    • パスワード

    from collections import deque

def differences_cnt(word1, word2):
    differences = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            differences += 1
    return differences

def solution(begin, target, words):
    answer = 0

    if target not in words:
        return 0

    q = deque()
    visited = [begin]
    q.append((begin,0))

    # bfs 시작
    while q:
        cur_word, depth = q.popleft()

        if cur_word == target:
            answer = depth
            break

        for word in words:
            if differences_cnt(cur_word, word) == 1 and word not in visited:
                visited.append(word)
                q.append((word, depth+1))      

    return answer

    😊 に感銘を与える


    レベル3なので、怖くなったのか、最初はどうやって解けばいいのか分からなかった.
    また,以前に解いたDFS,BFSの問題はいずれも隣接するノードによって与えられていたが,この問題は疎かで,私自身が「隣接する条件」を探さなければならないためである.
    それ以外に基本的なBFSアルゴリズムは何の応用もないので,問題を容易に解決できる.
    210825[42]大邱AI学校普通課程Webプログラミング14 Youtube 2左側エリアURL
    プログラマ