Bishop > 문제은행

본문 바로가기


실전대비 Level3

1290 : Bishop

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 22 회    시도횟수: 104 회   



“N×N 의 체스판에 Queen이 서로 공격하지 않도록 놓을 수 있는 방법을 찾아라.”

 

위 문제는 유명한 N-Queen 문제이다. 자료구조 시간에 N-Queen 문제를 풀면서 백트래킹을 마스터했다고 생각한 LIBe는 보다 더 어려운 문제를 풀이보기 위해서 문제를 다음과 같이 변경하였다.

 

“체스판에 장애물들이 있고, Queen이 장애물을 넘어갈 수 없을 때 최대로 놓을 수 있는 Queen의 개수는 몇 개일까?”

 

그러나 세상의 모든 일은 생각대로 되지 않는 법. 코딩 스킬이 부족했던 LIBe는 위 문제를 풀다가 포기하고 결국 문제를 다음과 같이 변경하였다.

 

체스판에 장애물들이 있고, Bishop이 장애물을 넘어갈 수 없을 때 최대로 놓을 수 있는 Bishop의 개수를 찾는 프로그램을 작성하시오.
(Queen은 가로, 세로, 대각선으로 이동할 수 있으나, Bishop는 대각선으로만 이동이 가능하다.)


입력은 여러 개의 테스트 케이스로 주어진다. 입력의 첫 줄에는 테스트 케이스의 개수 T(1≤T≤100)가 들어온다.
각각의 테스트 케이스의 첫 줄에는 체스판의 크기 N(1≤N≤8)이 주어진다.
이후 N 줄에는 체스판의 상태가 주어진다.
'.'은 Bishop을 놓을 수 있는 곳이며, '*'은 장애물이다.


각각의 테스트 케이스들에 대해 최대로 놓을 수 있는 Bishop의 개수를 출력한다.

[Copy]
2 
5 
..... 
..... 
..... 
..... 
..... 
8
..**.*.* 
**.***.* 
*.**...* 
.*.**.** 
*.**.*.* 
..**.*.* 
...*.*.* 
**.*.*.*
[Copy]
8
18




Ajou U Programming Contest, 1st, algospot BISHOPS

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.