DICTIONARY (Python3) 도저히 무엇이 잘못되어 런타임 오류가 나는지 모르겠습니다ㅠㅠ

  • KkanTo
    KkanTo

    안녕하세요??
    DICTIONARY 문제를 푸는 와중에, 계속해서 Runtime error가 나서 질문 드리게 되었습니다.

    사용 언어는 Python3이고,
    Graph는 인접 행렬로 표현하였습니다.

    ... 도저히 무엇이 문제를 만들고 있는지 모르겠습니다ㅠ.ㅠ

    도와주세요!! ㅠ.ㅠ 감사합니다!!
    (혹시, 특히 입력 부분에서 개선점이 있다면 알려주세요ㅠㅠ)

    def dfs(graph, visited, here, visited_vs):
    
        visited[here]=True
    
        neighbors=[i for i in range(26) if graph[here][i]==1]
    
        for neighbor in neighbors:
            if visited[neighbor]==False:
                visited, visited_vs=dfs(graph, visited, neighbor, visited_vs)
    
        visited_vs.append(here)
    
        return visited, visited_vs
    
    def dfsAll(graph):
    
        visited=[False for i in range(26)] # 어차피 알파벳
    
        temp=[]
        for v in range(26):
            if visited[v]==False:
                visited_vs=[]
                visited, visited_vs=dfs(graph, visited, v, visited_vs)
    
                # visited_vs.reverse() # reverse를 해야 topological sorting이 가능? 
                temp+=visited_vs
    
        temp.reverse() # 먼저 순서로 만들어 주기 위해 다시 뒤집기?
    
        answer=''
        for t in temp:
            answer+=chr(t+97)
    
        return answer
    
    def getAnswer(words):
        graph=[[0 for i in range(26)] for i in range(26)] # 그래프의 인접행렬표현
        # 'a':0, 'b':1 ... 하려면... ord(character)-ord('a')
    
        # Make graph
        for w in range(len(words)-1):
            word1=words[w]
            word2=words[w+1]
    
            for i in range(len(word1)): # 앞 단어가 끝날때까지만 보면 됨
                c1=word1[i]
                c2=word2[i]
                if c1!=c2:
                    graph[ord(c1)-ord('a')][ord(c2)-ord('a')]=1
                    break
    
        # Check cycle
        for i in range(26):
            for j in range(i, 26):
                if graph[i][j]+graph[j][i]==2:
                    return "INVALID HYPOTHESIS"
    
        # Make topological sorting
        answer=dfsAll(graph)
        return answer
    
    if __name__=="__main__":
        n=int(input())
    
        answers=[]
    
        for i in range(n):
            nbwords=int(input())
            words=[]
            for j in range(nbwords):
                words.append(input())
    
            answer=getAnswer(words)
            answers.append(answer)
    
        for answer in answers:
            print(answer)
    

    5달 전
1개의 댓글이 있습니다.
  • KkanTo
    KkanTo

    우선, 아래 코드에서, 앞 단어만 끝날때까지로 하면 안되었습니다.
    for i in range(len(word1)): # 앞 단어가 끝날때까지만 보면 됨

    그리고, indentation도 문제가 있었더라구요ㅎㅎ 해결했습니다!


    5달 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.