[Java] 백준 12946번 육각 보드

브루트포스 문제입니다.

육각보드의 일부분을 색칠하려고 합니다.
이 때 인접한 곳과 색이 같지않게 했을 때 최소의 색의 수를 구해야합니다.

육각보드에 모두 색을 칠할 경우 3개의 색만 있으면 모두 칠할 수 있습니다.
이것을 활용해서 DFS로 문제를 풀었습니다.

ex) 0 = X색, 1 = Y색
처음에 0을 넣고 다음번엔 1을 넣는 방식으로 반복합니다.
이 때 매번 인접한 칸을 확인하는데 현재 넣을 값과 같은곳이 있다면 3번째 색을 넣는 경우로 판단하였습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
  static int n;
  static int[][] map;
  static int[][] visit;
  static int result;

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    n = Integer.parseInt(br.readLine());
    map = new int[n][n];
    visit = new int[n][n];
    result = 0;

    for (int i = 0; i < n; ++i) {
      String s = br.readLine();
      for (int j = 0; j < n; ++j) {
        if (s.charAt(j) == '-') {
          map[i][j] = 0;
        } else {
          map[i][j] = 1;
        }
        visit[i][j] = -1;
      }
    }

    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (map[i][j] == 1 && visit[i][j] == -1) {
          dfs(i, j, 0);
        }
      }
    }

    bw.write(result + "\n");
    bw.close();
  }

  public static void dfs(int y, int x, int cnt) {
    int[] dy = { 0, 1, -1, 1, -1, 0 };
    int[] dx = { -1, -1, 0, 0, 1, 1 };

    visit[y][x] = cnt;
    result = Math.max(result, 1);

    for (int k = 0; k < 6; ++k) {
      int nextY = y + dy[k];
      int nextX = x + dx[k];

      if (nextY < 0 || nextX < 0 || nextY >= n || nextX >= n) {
        continue;
      }

      if (map[nextY][nextX] == 1 && visit[nextY][nextX] == -1) {
        dfs(nextY, nextX, 1 - cnt);
        result = Math.max(result, 2);
      }

      if (visit[nextY][nextX] == cnt) {
        result = 3;
      }
    }
  }
}