숌 사각형

시간 제한2초메모리 제한128 MB

요약
N x N 격자를 0부터 D-1까지의 숫자로 채워 모든 행과 열에 D개의 값이 전부 나타나도록 하면서 사전순으로 가장 작은 격자를 구합니다.
난이도

보통10점 중 6점

유형
백트래킹, 그리디, 행렬
정답자
아직 제출이 없습니다

문제

숌 사각형은 두 자연수 N과 D로 정해지는 N x N 크기의 정사각형이다. 각 칸에는 0 이상 D-1 이하의 정수 하나를 쓴다.

올바른 숌 사각형이 되려면 모든 행과 모든 열이 정수 0, 1, ..., D-1을 각각 적어도 한 번씩 포함해야 한다.

N과 D가 주어졌을 때, 가능한 숌 사각형 중 사전순으로 가장 앞서는 것을 출력하라. 사전순은 첫 행의 왼쪽 칸부터 오른쪽으로, 이후 행도 같은 방식으로 이어서 숫자를 비교한다.

입력

첫째 줄에 N과 D가 주어진다. N은 10 이하의 자연수이고, D는 N 이하의 자연수이다.

출력

N개의 줄에 걸쳐 숌 사각형을 출력한다. 한 행에서 인접한 두 수는 공백 하나로 구분한다.

예제4

  1. 예제 1

    입력
    3 3
    예상 출력
    0 1 2
1 2 0
2 0 1

  2. 예제 2

    입력
    5 2
    예상 출력
    0 0 0 0 1
0 0 0 0 1
0 0 0 0 1
0 0 0 0 1
1 1 1 1 0

  3. 예제 3

    입력
    5 4
    예상 출력
    0 0 1 2 3
0 0 1 2 3
1 1 0 3 2
2 2 3 0 1
3 3 2 1 0

  4. 예제 4

    입력
    9 7
    예상 출력
    0 0 0 1 2 3 4 5 6
0 0 0 1 2 3 4 5 6
0 0 0 1 2 3 4 5 6
1 1 1 0 3 2 5 6 4
2 2 2 3 0 1 6 4 5
3 3 3 4 5 6 0 1 2
4 4 4 2 6 5 1 0 3
5 5 5 6 1 4 2 3 0
6 6 6 5 4 0 3 2 1