N Rook Problem 2

문제 설명

각 칸에 자연수가 작성된 n $\times$ n 크기의 체스판 board가 주어집니다. 이 체스판 위에 n 개의 룩(Rook)을 서로 공격할 수 없도록 배치했을 때, 각각의 룩이 놓인 칸에 작성된 숫자 합의 최댓값을 반환하는 solution 함수를 작성하시오.

참고 내용

• N-Rook 문제(N-Rook problem)는, n $\times$ n 체스판 위에 n 개의 룩을 서로 공격할 수 없도록 배치하는 문제입니다.
• 룩(Rook)은 체스판에서 상, 하, 좌, 우 4방향으로 거리 상관없이 이동할 수 있습니다.

제한 사항

• n은 2 이상 10 이하의 자연수입니다.
• board[i][j]는 체스판의 (i+1, j+1) 위치에 작성된 숫자를 나타내며, 1 이상 100 이하의 자연수입니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 체스판의 (1,2), (2,1) 위치에 룩을 배치했을 때 최댓값 13을 반환합니다.

2번 테스트케이스 설명

• 체스판의 (1,2), (2,1), (3,3) 위치에 룩을 배치했을 때 최댓값 25를 반환합니다.

3번 테스트케이스 설명

• 체스판의 (1,2), (2,3), (3,4), (4,1) 위치에 룩을 배치했을 때 최댓값 31을 반환합니다.