단어 사다리

당연히 런타임 에러가 날것같은 존나긴코드 당연히 런타임에러. 그래푸와 dfs로 풀어봄.

근데 돌아가긴함. 나는 그래프를 잘모름.. 어떻게 축소할지도 아직잘모름..이틀안에 이게 바뀌면 좋겠다.

class Vertex:
  def __init__(self, key):
    self.id = key
    self.connectedTo = {}
    self.visited = False

  def addNeighbor(self,nbr,weight=0):
    self.connectedTo[nbr] = weight

class Graph:
  def __init__(self):
    self.vertList = {}

  def addVetex(self,key):
    nv = Vertex(key)
    self.vertList[key] = nv
    return nv

  def addEdge(self,f,t,cost=0):
    if f not in self.vertList:
      self.addVetex(f)
    if t not in self.vertList:
      self.addVetex(t)

    self.vertList[f].addNeighbor(self.vertList[t],cost)

  def dfs(self,word):
    start = self.vertList[word]
    output = [word]
    start.visited = True

    for nbr in start.connectedTo:
      if self.vertList[nbr.id].visited == False:
        output.extend(self.dfs(nbr.id))

    return output

def buildGraph(wordList):
  d = {}
  g = Graph()
  check = 0

  for line in wordList:
    for i in range(len(line)):
      bucket = line[:i] + '_' + line[i+1:]
      if bucket in d:
        d[bucket].append(line)
      else:
        d[bucket] = [line]

  for bucket in d.keys():
    for w1 in d[bucket]:
      for w2 in d[bucket]:
        if w1 != w2:
          g.addEdge(w1,w2)

  a = g.dfs(wordList[0])
  if wordList == a:
    return 'Correct'

  return 'Incorrect'


def read_input():
  wordList = []
  check = 0

  while True:
    word = input()
    if word == '#':
      if len(wordList) == 0:
        break
      else:
        print(buildGraph(wordList))
        wordList = []
        continue
    else:
      wordList.append(word)

read_input()