ORDERING 문제 오답 질문입니다.. (py3)

  • furyhunter
    furyhunter

    ORDERING

    위상정렬을 이용하여 구현해봤는데
    해당 작업을 하기 위해 필요한 작업의 수를 in_list에 넣고,
    해당 작업에 의존 관계가 있는(즉, 해당 작업을 수행하고 나서 수행할 수 있는) 작업들을 out_list에 저장했습니다.
    그 다음 in_list의 값이 0인것을 탐색해 out_list를 하나씩 제거하면서 해당 작업의 in_list 값을 줄였습니다.
    그 결과 in_list 값이 0이고 out_list 값도 없는 작업은 work_list 리스트에 저장을 하고
    이 작업은 완료되었음을 알리기 위해 in_list와 out_list의 값을 각각 -1과 *로 변경하였습니다.
    이 과정을 work_list가 모두 채워질때까지 반복합니다.

    작업을 시작할 때도 알파벳 순서대로 작업을 수행하고, out_list도 사전순으로 순회하도록 해서
    의존관계가 없는 작업들도 사전순으로 출력하도록 했습니다.

    혹시 오류가 보이시거나 문제가 생기는 테스트 케이스를 알고 계신다면 알려주시면 감사하겠습니다..

    alphabet = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 
            'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

import sys

n = int(sys.stdin.readline())

for i in range(0, n) : 
    work_list = [ ]
    index_list = [ ]
    input = sys.stdin.readline().split()

    alphabet_length = int(input[0])
    dependency_length = int(input[1])

    in_list = [ ]
    out_list = [ ]

    for j in range(0, alphabet_length) : 
        in_list.append(0)
        out_list.append("")

    for j in range(0, dependency_length) : 
        data = sys.stdin.readline().strip()

        dependency1 = data[0].strip()
        dependency2 = data[1].strip()

        in_list[alphabet.index(dependency2)] += 1
        out_list[alphabet.index(dependency1)] += dependency2

    for j in range(0, alphabet_length) : 
        out_list[j] = "".join(sorted(out_list[j]))

    j = 0

    while j < alphabet_length : 
        flag = 0
        if in_list[j] == 0 : 
            target = alphabet[j]
            k = 0
            if out_list[j] != '*' : 
                while  k < len(out_list[j]) : 
                    if flag == 0 : 
                        target = out_list[j][k]
                    in_list[alphabet.index(out_list[j][k])] -= 1
                    out_list[j] = out_list[j].replace(out_list[j][k], '')

                    flag = 1

            if len(out_list[j]) == 0 : 
                in_list[j] = -1
                out_list[j] = '*'
                work_list.append(alphabet[j])

                if flag == 1 : 
                    j = alphabet.index(target)
                    continue

        j = (j + 1) % alphabet_length

        if len(work_list) == alphabet_length : 
                j = 27

    answer = ""

    for j in range(0, alphabet_length) : 
        answer += work_list[j]

    print(answer.strip())

    8년 전
1개의 댓글이 있습니다.
  • seico75
    seico75

    1
    3 1
    BA

    정답은 BAC 이어야 할 것 같은데 올리신 소스는 BCA가 나올 것 같습니다.

    j = (j + 1) % alphabet_length
    이 부분이 적절한 j를 찾은 후에 j+1 를 하는데, 이것이 아니라 j 초기화해서 처음부터 찾아야 할 것 같네요.


    8년 전 link

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