체스에서 rook이란 가로 세로로 움직이는 말이다.

아래와 같이 특이한 NxN크기의 체스판이 주어졌을 때, 서로 공격 할 수 없게 놓을 수 있는 rook의 최대 개수인지 알아내는 프로그램을 작성해보자.

위 그림에서 빈칸은 하얀색, 막혀있는 칸은 검은색, rook은 원을 뜻한다.

(왼쪽부터)

첫 번째 그림의 경우 아무것도 안 놓았을 때, 체스 판을 뜻한다.

두 번째의 경우는 5개의 rook이 가능한 경우를 뜻한다.

첫 번째 줄의 경우 원래는 두 개의 rook이 서로 공격 가능하나 사이에 막힌 벽이 있기 때문에 공격이 불가능하다.

세 번째 역시 가능한 경우이고 이 경우에는 3개이다.

네 번째와 다섯 번째의 경우 서로 공격 할 수 있는 위치에 있기 때문에 이는 불가능한 경우이다.

Rook 배치하기 timer 1s memory 64MB

Rook 배치하기 1s 64MB