차수열
시간 제한2초메모리 제한128 MB
N개 정점에 대한 차수 수열이 주어질 때 이를 정확히 만족하는 단순 그래프의 인접 행렬을 하나 구성하거나 불가능하면 -1을 출력합니다.
문제
방향이 없는 그래프에서 한 정점에 연결된 간선의 개수를 그 정점의 차수라고 한다.
그래프의 각 정점 차수를 정점 번호 순서대로 나열하면 하나의 수열을 얻을 수 있다. 이 수열을 차수열이라고 한다. 임의의 차수열이 주어졌을 때, 그 차수열을 갖는 단순 무방향 그래프를 하나 구성하시오.
그래프의 간선은 방향이 없고, 한 정점에서 자기 자신으로 이어지는 간선은 없어야 한다. 그래프가 연결되어 있을 필요는 없지만, 입력으로 주어진 차수열은 반드시 정점 번호 순서와 그대로 대응되어야 한다.
입력
첫째 줄에 정점의 개수 N이 주어진다. (2 <= N <= 2,000)
둘째 줄에는 차수열을 이루는 N개의 정수가 공백으로 구분되어 주어진다. 각 정수는 0 이상 N - 1 이하이다.
출력
첫째 줄부터 N개의 줄에 걸쳐 구성한 그래프의 인접 행렬을 출력한다. 인접 행렬의 각 원소는 0 또는 1이어야 한다.
가능한 그래프가 여러 개라면 그중 아무 그래프나 출력해도 된다. 조건을 만족하는 그래프가 존재하지 않으면 첫째 줄에 -1만 출력한다.