[BOJ 백준] 16988 - Baaaaaaaaaduk2 (Easy), Java(자바)

문제

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

16988번: Baaaaaaaaaduk2 (Easy)

풀이

3 <= N, M <= 20 이어서 Brute Force + dfs로 해결했다. 바둑돌을 둘 수 있는 지점을 조합으로 구해 바둑돌을 놓고, 해당 상태에서 죽일 수 있는 상대 돌의 최대 갯수를 dfs로 구해 최댓값과 비교 후 출력한다.

코드

import java.util.*;
import java.io.*;

public class Main {
    static int N, M, sum, count, max;
    static boolean flag;
    static List<int[]> blank;
    static int[][] map;
    static int[][] delta = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static boolean[][] visited;
    
    public static void main(String args[]) throws Exception {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      N = Integer.parseInt(st.nextToken());
      M = Integer.parseInt(st.nextToken());
      max = 0;
      map = new int[N][M];
      visited = new boolean[N][M];
      blank = new ArrayList<int[]>();
      
      for (int i = 0; i < N; i++) {
          st = new StringTokenizer(in.readLine());
          for (int j = 0; j < M; j++) {
              map[i][j] = Integer.parseInt(st.nextToken());
              if (map[i][j] == 0)
                blank.add(new int[] {i, j});
          }
      }
      
      sum = 0;
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!visited[i][j] && map[i][j] == 2) {
                    count = 1;
                    flag = true;
                    visited[i][j] = true;
                    dfs(i, j);
                    sum += flag ? count : 0;
            }
        }
      }
      
      for (int first = 0; first < blank.size() - 1; first++) {
          map[blank.get(first)[0]][blank.get(first)[1]] = 1;
          for (int second = first + 1; second < blank.size(); second++) {
              map[blank.get(second)[0]][blank.get(second)[1]] = 1;
              visited = new boolean[N][M];
              sum = 0;
              for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (!visited[i][j] && map[i][j] == 2) {
                        count = 1;
                        flag = true;
                        visited[i][j] = true;
                        dfs(i, j);
                        sum += flag ? count : 0;
                    }
                }
              }
              max = Math.max(max, sum);
              map[blank.get(second)[0]][blank.get(second)[1]] = 0;
          }
          map[blank.get(first)[0]][blank.get(first)[1]] = 0;
      }
      System.out.println(max);
    }
    
    static void dfs(int r, int c) {
        for (int d = 0; d < delta.length; d++) {
            int dr = r + delta[d][0];
            int dc = c + delta[d][1];
            if (dr < 0 || dc < 0 || dr >= N || dc >= M || visited[dr][dc] || map[dr][dc] == 1)
                continue;
            if (map[dr][dc] == 0) {
                flag = false;
                continue;
            }
            visited[dr][dc] = true;
            count++;
            dfs(dr, dc);
        }
    }
}