글 읽기 - [파이썬] 틀린 부분 알려주시거나 반례 주시면 감사하겠습니다.

eyescat123 1년 전 0

위상정렬로 풀었고 예제는 맞는데 결과는 틀립니다.

블로그로 찾은 예제들로 해봤을 때에도 맞게 나와서 어디가 틀렸는지 도통 모르겠어서 질문 올립니다.

코드에 틀린 부분 집어주시거나 반례 주시면 정말 감사하겠습니다!

import sys
from collections import deque
T = int(input())
for _ in range(T):
    n = int(sys.stdin.readline())  # 팀 수
    t = list(map(int, sys.stdin.readline().split()))  # 작년 등수
    m = int(sys.stdin.readline())
    change = []  # 등수 바뀐 쌍
    for _ in range(m):
        a, b = map(int, sys.stdin.readline().split())
        change.append((a, b))

    edges = []  # 그래프 -> 간선
    for i in range(n-1):
        for j in range(i+1, n):
            a, b = t[i], t[j]
            if (a, b) in change or (b, a) in change:  # 간선 순서 바꾸기
                edges.append((b ,a))
            else:
                edges.append((a, b))
    
    # 간선 -> 그래프
    graph = [[] for _ in range(n+1)]
    for edge in edges:
        a, b = edge
        graph[a].append(b)
    
    indegree = [0] * (n+1) 
    q = deque()
    # indegree 초기화
    for edge in edges:
        a, b = edge
        indegree[b] += 1
    # indegree=0 인 것들 q에 push
    for d in range(1, n+1):
        if indegree[d] == 0:
            q.append(d)
    answer = []
    
    if len(q) == 0:
        print('IMPOSSIBLE')
        break
    while q:
        if len(q) > 1: # indegree가 같은 게 여러개 => 답이 여러개 될 수 있음
            print('?')
            break
        now = q.popleft()
        answer.append(now)
        # now와 연결된 애들 indegree-1 
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)
    if len(answer) != n:
        print('IMPOSSIBLE')
        break

    for a in answer:
        print(a, end=' ')

cdg0228 1년 전 0

저도 아직 풀지 못한 상태라 코드의 로직이 맞는지 알 수는 없지만 출력초과가 나올 것 같습니다!

len(q)==0이라면 'IMPOSSBILE"을 출력하고 42줄에서 break를 만나게 되는데, 이 break는 테스트케이스만큼 돌고 있는 반복문을 중지시켜 버립니다:)

56번째 break도 마찬가지구요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[파이썬] 틀린 부분 알려주시거나 반례 주시면 감사하겠습니다.

eyescat123 1년 전 0

cdg0228 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말