글 읽기 - 어느부분이 잘못되었을까요 ?..

tkddn0811 2년 전 0

위상정렬로 접근해서

주어지는 행렬에대한 그래프를 따로 만들고 그 그래프를이용 1차로 위상정렬한 값을 result 리스트에 담은후

원소의 값과 인덱스 값을 치환하여 ans 리스트에 담아 출력했는데 예시만 맞네요..

답이 여러개인경우 사전순 정렬이라하여 애초에 진입차수가 0인것을 우선순위큐로 넣어주었습니다.

반례가 있을까요?

import sys
import heapq
input = sys.stdin.readline

N = int(input())

graph = [[] for _ in range(N+1)]
indegree = [0]*(N+1)
v_info = [list(map(int, input().strip()))for _ in range(N)]

for i in range(N):
    for n in range(N):
        if v_info[i][n] == 1:
            graph[i+1].append(n+1)
            indegree[n+1] += 1
result = []
ans = [[] for _ in range(N+1)]


def topology_sort():
    q = []
    for i in range(1, N+1):
        if indegree[i] == 0:
            heapq.heappush(q, i)
    while q:
        now = heapq.heappop(q)
        result.append(now)
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                heapq.heappush(q, i)


topology_sort()

if len(result) != N:
    print(-1)
else:
    for index, b in enumerate(result):
        ans[b] = index+1
    for i in range(1, N+1):
        print(ans[i], end=' ')

kdh6429 2년 전 0

아래 입력에 대한 결과가 이상합니다.

입력

5
11000
00100
10010
00010
00000

출력

[] [] [] [] 1

정답

-1

tkddn0811 2년 전 0

result에 값이 하나라도 있을경우 ans에 추가하는경우가 생겨 result리스트의 길이가 N이 아닌경우는 사이클이 존해하는 경우로 -1이 되도록 수정하였지만 그래도 틀리다고 나오네요 ..

tkddn0811 2년 전 1

outdegree를 기준으로 수정하였더니 통과하였습니다 .

반례는 아래와 같았습니다.

4
0011
0000
0000
0100

기존 알고리즘의 결과 : 1 4 2 3
알고리즘의 결과(정답) : 1 3 4 2

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

문제

문제

출처

ICPC

어느부분이 잘못되었을까요 ?..

tkddn0811 2년 전 0

kdh6429 2년 전 0

tkddn0811 2년 전 0

tkddn0811 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말