Rook 배치하기 > 문제은행

본문 바로가기


실전대비 Level2

1122 : Rook 배치하기

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



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

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

 

 

e3050b66a1b29a01767400d7560a4131_1449730
 

 

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

(왼쪽부터) 첫 번째 그림의 경우 아무것도 안 놓았을 때, 체스 판을 뜻한다. 두 번째의 경우는 5개의 rook이 가능한 경우를 뜻한다. 첫 번째 줄의 경우 원래는 두 개의 rook이 서로 공격 가능하나 사이에 막힌 벽이 있기 때문에 공격이 불가능하다. 세 번째 역시 가능한 경우이고 이 경우에는 3개이다. 네 번째와 다섯 번째의 경우 서로 공격 할 수 있는 위치에 있기 때문에 이는 불가능한 경우이다.


첫 번째 줄에는 체스 판의 크기를 뜻하는 숫자 N(1≤N≤4)가 입력된다. 그 다음 줄부터 N개의 줄에 걸쳐서 체스 판의 정보가 들어온다. 체스 판의 크기는 NxN이며(따라서 N개의 줄에 길이 N의 문자열이 각각의 행을 의미한다.) 막힌 부분은 'X' 비어있는 부분은 '.'로 표시되어진다.



입력 받은 체스 판에 놓을 수 있는 최대 rook의 개수를 출력한다.


[Copy]
4
.X..
....
XX..
....
[Copy]
5




Mid-Central USA 1998, poj 1315

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.