1432번: 그래프 수정

문제

N개의 정점이 있는 그래프가 주어지면, 다음과 같은 방법에 의해서 정점의 번호를 다시 매기고 싶다.

모든 그래프의 번호는 1보다 크거나 같고 N보다 작거나 같은 번호를 가져야 한다.

만약 V1에서 V2로 연결된 간선이 있다면, V2의 번호는 V1보다 커야 한다.

위와 같은 조건을 이용해서 그래프의 번호를 다시 매긴 후에, 1번 정점의 새로 고친 번호를 M1, 2번 정점의 새로 고친 번호를 M2, ..., N번 정점의 새로 고친 번호를 MN이라고 하면, N개의 수열이 만들어진다.

이 수열을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 인접행렬 형식으로 입력이 주어진다. 0은 연결되지 않았음을 의미하고, 1은 연결되었다는 것을 의미한다. N은 50보다 작거나 같은 자연수이다.

출력

첫째 줄에 수열의 각 원소를 차례대로 공백을 사이에 두고 출력한다. 만약 그래프의 번호를 수정할 수 없다면 -1을 출력한다. 답이 여러 개일 경우에는 사전 순으로 제일 앞서는 것을 출력한다.

풀이

수열을 찾아내라는 말이 어떤 말인가?

예제의 그래프에서 각 노드들을 위상 정렬을 통해 나타내어본다면 [1,2,4,5,3] [2,1,4,5,3] [2,1,4,5,3]... 등과 같이 나타낼 수 있겠다. 여기서 우리는 가장 끝 노드의 번호를 가장 큰 번호로 바꾸어야 한다.

• 예를 들어 [1,2,4,5,3] 그래프는 [1,2,3,4,5] 그래프로 바뀔 것이다.
• 여기서 4번 정점 → 3번, 5번 정점 → 4번, 3번 정점→ 5번으로 바뀌었으므로
• 각 정점들을 바뀐 번호로 나열해보면 {1번:1번, 2번:2번, 3번:5번, 4번:3번, 5번:4번}, 이를 [1,2,5,3,4]의 순열로 만들 수 있다.
• 즉 각 노드들이 몇 번째에 입력받았는지를 노드 번호 순서대로 알고 싶은 것이다.

이것을 다시 공의 무게로 치환해서 생각해보면