word_transform_dfs.py

# -*- coding: utf-8 -*-
# from : https://programmers.co.kr/learn/courses/30/lessons/43163?language=python3

class Node:
  def __init__(self, data):
    self.visited = False
    self.data = data

class Stack:
  def __init__(self):
    self.items = []
  
  def isEmpty(self):
    return self.items == []
  
  def push(self, item):
    self.items.append(item)
  
  def pop(self):
    return self.items.pop()

  def top(self):
    return self.items[len(self.items) - 1]

  def size(self):
    return len(self.items)

# dfs 재귀함수에서 계속 재사용되기 때문에 Global 변수로 지정한다
stack = Stack()
wordLength = 0
shortest = 50 # 문제에서 단어의 개수가 최대 50개라고 했으므로 최악의 경우 50번 변환이 일어날 수 있기 때문에, 50으로 초기화
target = ""
words = []

def solution(b, t, ws):

  # 함수 외부에있는 Global 변수에 값을 할당하기 위해서는 이렇게 global keyword를 붙여줘야한다
  global wordLength
  global target
  global words

  target = t
  stack.push(b)
  wordLength = len(b)

  # word을 Node Object로 만든다. 그래야 해당 word에 방문 했는지 안했는지를 표시할 수 있다
  for i in range(len(ws)):
    ws[i] = Node(ws[i])
  words = ws

  # words배열에 target이 있는지 체크한다
  if not targetExistCheck(target, words):
    return 0

  # 깊이 우선 탐색 시작(과 끝)
  dfs()

  # 깊으 우선 탐색으로 찾은 최단경로를 리턴
  return shortest

def dfs():
  # 값을 할당해야 하기 때문에 global keyword를 붙여준다
  global shortest
  
  # stack의 size가 0이라는것은 더이상 target에 도달하는 길이 없다는 의미이다
  if stack.size() == 0:
    return

  # stack에 맨 위에있는 word를 가져온다. pop() 과는 다름!
  top = stack.top()

  # words를 loop돌면서 top과 유사한 다른 word를 찾는다
  for i in range(len(words)):

    # 이미 방문했다면 pass
    if words[i].visited:
      continue
    
    # 단어끼리의 유사성 검사진행(딱 하나의 character만 다른경우 = 유사하다)
    result = wordSimilarityCheck(top, words[i].data, wordLength)
    if result:
      # 유사할 뿐만 아니라, 우리가 찾던 target과 같다면 shortest에 stack의 size를 저장한다. stack의 size가 결과적으로 path의 길이이다.
      if words[i].data == target:

        # 현재까지의 최단경로보다 더 짧다면, 갱신
        if shortest > stack.size():
          shortest = stack.size()
        
        # 이제 이 word에서는 더이상 유사한걸 찾아봤자 의미 없기 때문에(한칸보다 짧을 수는 없으니까) stack에서 pop하고 return해서 loop를 멈춘다.
        # 재귀함수니까 그전에 진행되던 loop는 계속 진행됨
        stack.pop()
        return
      
      # 무한 루프에 빠지지 않도록 방문 표시를 한다
      words[i].visited = True

      # 유사성은 있으나 target과는 다르다면 stack에 push해서 dfs()로 계속 찾아 내려간다.
      stack.push(words[i].data)
      dfs()
  
  stack.pop()

def targetExistCheck(target, words):
  exist = False
  for i in range(len(words)):
    if words[i].data == target:
      exist = True

  return exist

# 글자 사이의 유사성 체크를 한다.
# 단어가 한글자만 빼고 나머지가 character 및 위치까지 같다면 유사하다고 판정되기 때문에,
# 달라도 되는 그 한글자를 "_"로 대체하고 그냥 단어끼리 비교한다
def wordSimilarityCheck(left, right, length):
  tempL = left
  tempR = right
  for i in range(length):
    # string을 배열로 변환
    left = list(left)
    right = list(right)

    # 달라도 되는 위치의 character를 그냥 "_"로 대체한다
    left[i] = "_"
    right[i] = "_"

    # 배열을 다시 string으로 만든다. 그러면 "_it" vs "_mt" 이렇게 되니까 비교만 해주면 된다
    left = ''.join(left)
    right = ''.join(right)
    if left == right:
      return True
    
    # 원래 들어온 string을 살려서 다시 다음 루프때 써야하니까, 재할당 해준다
    left = tempL
    right = tempR

  return False


test1 = ["hot","dot","dog","lot","log","cog"]
test2 = ["hot","dot","dog","lot","log"]
print(solution("hit", "cog", test1)) # 4
print(solution("hit", "cog", test2)) # 0