아이스크림
시간 제한2초메모리 제한128 MB
최대 1000개 아이스크림에 대한 쌍별 선호 관계가 주어질 때, 인접 항목이 항상 선호되거나 동등한 순서를 찾거나 불가능함을 판별합니다.
문제
어떤 사람이 여러 아이스크림에 대해 선호 관계를 말한다. 두 아이스크림 A와 B에 대해 A를 B보다 더 좋아하거나, 둘을 비슷하게 좋아하거나, B를 A보다 더 좋아한다는 정보가 주어진다.
선호 관계가 항상 전이적이라면 모든 아이스크림을 한 줄로 배열하여, 앞에 있는 아이스크림이 뒤에 있는 모든 아이스크림보다 더 좋거나 비슷하게 좋다고 말할 수 있다. 하지만 실제 선호는 전이적이지 않을 수 있으므로, 여기서는 더 약한 조건인 일관성 선호도를 사용한다.
아이스크림 배열 I1, I2, ..., In이 있을 때, 모든 i = 1, 2, ..., n - 1에 대해 Ii를 Ii+1보다 더 좋아하거나 비슷하게 좋아하면 이 배열은 일관성 선호도에 따라 정렬되었다고 한다.
n개의 아이스크림 1, 2, ..., n과 모든 두 아이스크림 사이의 선호 관계가 주어진다. 일관성 선호도에 따라 정렬된 아이스크림 배열을 구하시오.
입력
첫째 줄에 정수 n(1 <= n <= 1,000)이 주어진다.
다음 n개의 줄에는 각각 n개의 문자가 주어진다. 이 중 i번째 줄의 j번째 문자 gi,j는 아이스크림 i와 아이스크림 j의 관계를 나타낸다.
- gi,j가 '
+'이면 아이스크림 i를 아이스크림 j보다 더 좋아한다. - gi,j가 '
-'이면 아이스크림 j를 아이스크림 i보다 더 좋아한다. - gi,j가 '
0'이면 두 아이스크림을 비슷하게 좋아한다.
항상 gi,i는 'x'이다. i와 j가 다르면 gi,j와 gj,i는 서로 모순되지 않게 주어진다. 즉, 한쪽이 '+'이면 다른 쪽은 '-'이고, 한쪽이 '0'이면 다른 쪽도 '0'이다.
출력
첫째 줄에 일관성 선호도에 따라 정렬된 아이스크림 번호의 배열을 출력한다. 가능한 배열이 여러 개이면 그중 아무거나 출력해도 된다.
일관성 선호도에 따라 정렬할 수 없으면 첫째 줄에 -1만 출력한다.