새로운 매직 스퀘어
시간 제한2초메모리 제한128 MB
1부터 25까지의 수를 5x5 격자에 채워 각 행이 왼쪽에서 오른쪽으로 증가하도록 하면서, 행마다 최대 한 칸의 기존 값을 유지하고 사전순으로 가장 작은 격자를 출력하거나 -1을 출력합니다.
문제
5 x 5 크기의 격자에 1부터 25까지의 정수를 각각 한 번씩 채워 넣으려고 한다. 각 행에서는 왼쪽에서 오른쪽으로 갈수록 수가 반드시 커져야 한다.
일부 칸에는 이미 수가 적혀 있을 수 있다. 이미 적힌 수는 한 행에 하나를 넘지 않으며, 나머지 빈칸을 모두 채워야 한다.
주어진 격자를 완성할 수 없다면 -1을 출력한다. 완성 방법이 여러 가지라면, 격자를 위에서 아래로, 각 행에서는 왼쪽에서 오른쪽으로 읽었을 때 사전순으로 가장 작은 격자를 출력한다. 즉, 먼저 1행 1열의 수가 작은 답을 고르고, 같다면 1행 2열, 그다음 1행 3열처럼 차례대로 비교한다.
입력
총 5개의 줄에 걸쳐 각 줄마다 5개의 정수가 공백으로 구분되어 주어진다. 빈칸은 0으로 주어진다. 0이 아닌 수는 이미 채워진 칸을 뜻한다.
출력
완성된 5 x 5 격자를 5개의 줄에 출력한다. 각 줄에는 해당 행의 5개 수를 공백으로 구분해 출력한다.
격자를 완성할 수 없다면 -1을 출력한다.