<Algorithm> 144. Baaaaaaaaaduk2[Easy](BJO)

1. 16988번 Baaaaaaaaaduk2[Easy](BJO)

• 백트래킹 문제

• 바둑돌을 둘때 여러 방이 생기는 경우에 대한 처리만 조심하면 된다.

import java.util.Scanner;
 
public class Main {
    static int n;
    static int m;
    static int[][] board;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        board = new int[n][m];
        /******************************
         * 백트래킹을 이용해서 모든 바둑 두는 경우를 
         * 구한다. 그리고 DFS 탐색을 이용해 바둑개수
         * 와 둘러 쌓여있는지 판단하고 가장 최대가 되는
         * 바둑알의 수를 구한다.
         *******************************/
        for(int i = 0; i < n ; i++) {
            for(int j = 0; j < m; j++) {
                board[i][j] = sc.nextInt();
            }
        }
        start(0);
        System.out.println(max);
    }
    static boolean visited[][];
    static int total;
    static int max = 0;
    public static void start(int deep) {
        if(deep == 2) {
            visited = new boolean[n][m];
            total = 0;
            for(int i = 0; i < n; i++) {
                for(int j = 0; j <m; j++) {
                    if(board[i][j] == 2 && !visited[i][j]) {
                        visited[i][j] = true;
                        ck = false;
                        count = 1;
                        dfs(i, j);
                        if(!ck) total += count;
                    }
                }
            }
            max = Math.max(max, total);
            return;
        }
        
        for(int i = 0; i < n ; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j] == 0) { // 0일때만 바둑 둘수 있음
                    board[i][j] = 1;
                    start(deep+1);
                    board[i][j] = 0;
                }
            }
        }
    }
    
   static boolean ck;
   static int count;
   static int[] dx = {0,0,1,-1};
   static int[] dy = {1,-1,0,0};
   public static void dfs(int x, int y) {
       for(int i = 0; i < 4; i++) {
           int nx = x + dx[i];
           int ny = y + dy[i];
           
           if(isBoundry(nx, ny) && !visited[nx][ny] && board[nx][ny] != 1) {
               visited[nx][ny] = true;
               if(board[nx][ny] == 0) ck = true;
               if(board[nx][ny] == 2) count++;
               dfs(nx, ny);
           }
       }
   }
   
   public static boolean isBoundry(int nx,int ny){
       if(nx >= 0 && ny >= 0 && nx < n && ny < m) {
           return true;
       }
       return false;
   }
   public static void print() {
       for(int i = 0; i < n ; i++) {
            for(int j = 0; j < m; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
   }
}
 

참고 & 출처