leejk9592   6년 전

위상정렬 단계 문제인 최종단계 문제를 풀려하는데, 제가 잘못 생각하고 있는 것인지 계속 틀립니다... ㅠㅠ


간단하게 제 알고리즘을 설명하자면

[1] 1등에서 N등(=꼴등) 까지 순위를 vector 자료형으로 입력 받는다.
orders[i] = input(i)

[2] 2중 for문으로 각 등수에 대해 자기보다 낮은 순위의 노드들로 방향 간선을 인접 배열로 만든다.
    이 때, 간선이 유입되는 쪽에 대해 카운트를 증가 시킨다, 카운트는 유입 간선 개수를 뜻한다.
for i  in 1...(N-1)
     for j in (i + 1)...N
         a = orders[i], b = orders[j]
         link[a][b] = true
         count[b]++

[3] m개의 바뀐 순위 쌍  a, b를 입력 받아 간선 방향을 바꾸고
    a의 카운트는 감소, b의 카운트는 증가시킨다.
link[a][b] = true
link[b][a] = false
count[a]--
count[b]++

[4] while문을 N번 돌며 카운트가 0인 팀을 출력하고, 다음 while문 개수 검사에서 제외
ㄴ카운트가 0인 팀이 2개 이상이면 while문을 중닫하고 "?"을
ㄴ카운트가 0인 팀이 없으면 역시 while문을 중단하고 "IMPOSSIBLE"을

핵심만 설명했는데... 이 알고리즘 아닌가요?

dotorya   6년 전

1. 입력으로 a와 b가 들어왔을 때, 작년 순위 기준으로 a가 b보다 높다는 말은 문제 조건에 없습니다.
a가 b보다 낮은 상태였는데 올해 순위에선 높은 것일수도 있습니다.

2. isCycle에 -1을 대입한 후 break를 해주셨는데, 이 과정에서 해당 테스트 케이스가 전부 입력되지 않고 중단되어 버립니다.
이렇게 구현하면 다음 테스트 케이스를 입력받을 때 이전 테스트 케이스 일부가 섞여 들어와 망가진 출력이 나옵니다.

3. 약간의 예외처리 문제가 있습니다.
현재 상태에서 2개 이상의 노드가 후보로 들어왔다고 해서 ?를 찍고 종료하는 게 항상 옳을까요?


leejk9592   6년 전

Thank You So Much
ㄳㄳ

rdd6584   6년 전

덕분에 해결했습니다. ㅠㅠㅠㅠ 문제에 혼동되는 부분이 있었네요 

kje7584   3년 전


3. 약간의 예외처리 문제가 있습니다.현재 상태에서 2개 이상의 노드가 후보로 들어왔다고 해서 ?를 찍고 종료하는 게 항상 옳을까요?

이부분이 항상 종료가 아닌가요..? 뭐가 있죠..?(동공지진)

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