[백준] 4672번 : Don't Get Rooked - 자바[Java]

https://www.acmicpc.net/problem/4672

풀이

체스판이 주어졌을 때 놓을 수 있는 최대 룩 개수를 구하는 문제다. 체스판은 빈 칸은 '.', 벽은 'X'로 되어있다. 룩은 벽을 통과하여 이동할 수 없다.

 

n-Queen 문제와 비슷하게 백트래킹을 사용하여 풀었다.

 

로직

1. 체스판을 입력하면서 빈 칸의 수를 카운트한다. 빈 칸의 수는 답(최대 룩 개수)이 될 수 있는 최댓값이기 때문에, 추후 탐색할 때 이미 해당 값을 구한다면 탐색을 더 이상 하지 않는다.

2. rook(0, 0, 0)을 호출한다.

 

rook(int r, int c, int count)

(r,c) 좌표에 룩을 놓을 수 있는지 검사한 후 놓을 수 있다면 rook(r, c+1, count+1)을 호출한다.

해당 칸을 스킵하는 경우도 있으므로 rook(r, c+1, count)도 호출한다.

마지막 칸까지 모두 탐색했다면 maxCount 값을 업데이트한다.

    static void rook(int r, int c, int count) {
        if (maxCount == remainRoom) { // 이미 최댓값을 찾은 경우
            return;
        }

        if (r == n-1 && c == n) { // 마지막 칸까지 다 탐색했다면 maxCount 업데이트
            maxCount = Math.max(maxCount, count);
            return;
        }

        if (c == n) { // 다음 줄로 이동
            r++;
            c = 0;
        }

        if (board[r][c] == '.' && check(r, c)) { // 해당 칸에 룩을 놓을 수 있는 경우
            board[r][c] = 'V';
            rook(r, c+1, count+1);
            board[r][c] = '.';
        }

        rook(r, c+1, count); // 룩을 놓을 수 있어도 해당 칸을 스킵하는 경우도 탐색
    }

check(int r, int c)

룩을 (r, c) 좌표에 놓을 수 있는지 여부를 반환한다. (r, c) 좌표를 중심으로 위쪽과 왼쪽 방향을 탐색할 때 벽을 만나는 경우 반복문을 탈출해야 한다.

아래쪽과 오른쪽 방향을 탐색하지 않아도 되는 이유는, 좌표를 순차적으로 왼쪽 열에서 오른쪽 열로, 위에서 아래 행으로 내려오면서 탐색하기 때문에, (r, c) 좌표를 기준으로 아래쪽과 오른쪽 방향에는 룩이 없기 때문이다.

    static boolean check(int r, int c) {
        // 위쪽과 왼쪽 방향에 룩이 있는지 탐색
        // 벽에 막히면 break

        int i = r - 1;
        for (; i >= 0; i--) {
            if (board[i][c] == 'X') {
                break;
            }
            if (board[i][c] == 'V') {
                return false;
            }
        }

        int j = c - 1;
        for (; j >= 0; j--) {
            if (board[r][j] == 'X') {
                break;
            }
            if (board[r][j] == 'V') {
                return false;
            }
        }

        return true;
    }

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int n;
    static char[][] board;
    static int remainRoom = 0;
    static int maxCount = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        while (true) {
            n = Integer.parseInt(br.readLine());
            if (n == 0) {
                break;
            }

            board = new char[n][n];
            remainRoom = 0; // 빈 칸의 수, maxCount가 될 수 있는 최댓값
            maxCount = 0; // 룩을 놓을 수 있는 최댓값

            for (int i = 0; i < n; i++) {
                String line = br.readLine();
                for (int j = 0; j < n; j++) {
                    board[i][j] = line.charAt(j);
                    if (board[i][j] == '.') {
                        remainRoom++;
                    }
                }
            }

            rook(0, 0, 0); // (0, 0) 좌표부터 시작

            sb.append(maxCount).append("\n");
        }

        System.out.println(sb);
    }

    static void rook(int r, int c, int count) {
        if (maxCount == remainRoom) { // 이미 최댓값을 찾은 경우
            return;
        }

        if (r == n-1 && c == n) { // 마지막 칸까지 다 탐색했다면 maxCount 업데이트
            maxCount = Math.max(maxCount, count);
            return;
        }

        if (c == n) { // 다음 줄로 이동
            r++;
            c = 0;
        }

        if (board[r][c] == '.' && check(r, c)) { // 해당 칸에 룩을 놓을 수 있는 경우
            board[r][c] = 'V';
            rook(r, c+1, count+1);
            board[r][c] = '.';
        }

        rook(r, c+1, count); // 룩을 놓을 수 있어도 해당 칸을 스킵하는 경우도 탐색
    }

    static boolean check(int r, int c) {
        // 위쪽과 왼쪽 방향에 룩이 있는지 탐색
        // 벽에 막히면 break

        int i = r - 1;
        for (; i >= 0; i--) {
            if (board[i][c] == 'X') {
                break;
            }
            if (board[i][c] == 'V') {
                return false;
            }
        }

        int j = c - 1;
        for (; j >= 0; j--) {
            if (board[r][j] == 'X') {
                break;
            }
            if (board[r][j] == 'V') {
                return false;
            }
        }

        return true;
    }
}