시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 1299 | 545 | 462 | 42.778% |
체스와 관련된 문제는 처음 알고리즘을 배우기 시작할 때 부터 접하게 된다. 가장 유명한 문제로는 N-Queen 문제가 있다. 이를 변형해서 N-Rook 문제를 만들 수 있다. Rook(룩) 은 체스에서 같은 행이나 같은 열의 아무 위치로 이동할 수 있는 체스 말이다.
N × N 크기의 체스판에 룩을 최대한 많이 어떻게 배치할까? 라는 문제는 매우 쉽게 해결할 수 있다. 대각선으로 룩을 배치하면 된다.
문제를 좀 더 어렵게 만들어서, N x N 크기의 체스판에 폰이 몇 개 놓여있다. 이런 상황에서 룩을 최대 몇 개 배치할 수 있을까? 폰이 배치 되어 있으면, 룩은 폰에게 가로막혀 같은 열이나 같은 행의 모든 위치에 이동할 수 없다.
첫 줄에 체스판의 크기 N이 주어진다. (1 ≤ N ≤ 100)
그리고 다음 N개의 줄에 체스판의 정보가 주어진다. '.'은 빈 칸을 의미하고, 'X'는 그 칸에 폰이 있음을 의미한다.
주어진 체스판에 룩을 배치할 때, 최대 몇 개를 배치할 수 있는지 출력한다.
5 X.... X.... ..X.. .X... ....X
7