옥상 3

문제는 더블릿 옥상에 있는 koi_Ebishop입니다.

문제 사이트 주소입니다.

http://183.106.113.109/pool/koi_Ebishop/koi_Ebishop.php?pname=koi_Ebishop

판 위에 비숍을 놓을 수 있는 최대 자리수를 구하는 문제입니다.  비숍은 대각선에 같은 비숍을 놓을 수 없으며 대각선의 비숍 유무와 관계없이 비숍을 놓을 수 없는 자리가 있습니다.

우선 이 문제는 백트래킹으로 풀었습니다.

일단 알아두면 좋은 것들은 한쪽 대각선방향(오른쪽 위에서 왼쪽 아래)으로 겹치지 않고 놓을 수 있는 수는 2*한쪽칸의 개수-1로 4*4 칸의 경우 7칸이 됩니다.  

재귀함수 탈출조건으로 쓰일겁니다.  예의 5*5인 경우 0, 0부터 4, 4까지 대각선으로 검사를 할 때 9번의 검사면 끝납니다.

또한 우상-좌하 대각선과 좌상-우하 대각선에서 겹치는 부분 

(우상-좌하 한줄 이미지가 없는데 이것도 포함입니다.)

위와 같은 선에 포함되는 칸은 같은 대각선에 있다고 볼 수 있는데 횡을 i, 열을 j라고 했을 때 i-(j-i)+열 혹은 행의수 를 하게 되면 해당 라인을 하나의 배열 인덱스로 놓고 검사할 수 있습니다.

3, 2와 2, 3 / 2, 1과 3, 2는 같은 라인에 있다는걸 알 수 있습니다.  이는 대각선 위치에 비숍이 있는지의 여부를 검사하는데 쓰입니다.

위 2가지 사항을 토대도 백트래킹을 돌리면됩니다.

시간을 단축하기 위해 i, j열을 받을 때 i와 j를 바꾸어도 비숍을 놓을 수 없는 자리는 따로 배열을 선언하여 표시합니다.

재귀 함수에서 이 값이 체크되어 있으면 어떻게든 비숍을 놓을 수 없기 때문에 추가 검사를 하지 않고 바로 다음으로 넘어갑니다.

또한 한번 비숍을 놓을 수 있는 개수 n를 구하면 다음 부터는 남아있는 검사라인과 지금까지 검사한 n을 더해 최대n보다 작을 경우 return을 해버립니다.

검사는 우상에서 좌하로

0, 0

(0, 1) (1, 0)

(0, 2) (1, 1) (2, 0)

으로 진행하며 비숍을 놓을 수 있고, 같은 라인에 놓아진 비숍이 없으면 비숍을 놓았고 해당 라인에 비숍이 있다는 체크를 하면서 다음 재귀를 호출합니다.

해당 재귀가 끝나면 다시 비숍을 빼주는 작업을 합니다.

끝까지 검사를 하였을 때 최대 비숍의 개수를 출력하면 됩니다.