[백준] 12946. 육각보드 (Java)

 

문제

12946번: 육각 보드

 

 

알고리즘

그래프, 깊이우선탐색(DFS)

 

 

풀이

육각 보드이므로 인접한 칸이 [상,하,좌,우]가 아니라 [상, 우상, 좌, 우, 하, 우하] 6가지이고,

임의의 칸과 인접한 6칸이 모두 색칠되어야하는 경우 3가지 색이면 모두 색칠할 수 있으므로 정답은 최대 3이 된다.

 

따라서 X인 칸을 시작으로 DFS를 진행하며 색을 칠한다.

색은 칠하지 않은 경우 0, 색칠된 경우 1, -1 로 표현한다.

 

인접한 칸이 아직 칠해지지 않았다면 칠해야하므로 정답은 최소 2가 되고, 다음 색(-c)으로 칠하기 위해 함수를 재귀 호출한다.

인접한 칸이 이미 칠해진 칸이고, 방금 색칠한 자신과 같은 색이라면 색이 겹치게 되므로 3번째 색을 써야한다.

따라서 문제에서 나올 수 있는 최댓값이므로 3을 출력하고 프로그램을 종료한다.

 

 

코드

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

public class Main {
	static int[] dy = { -1, -1, 0, 0, 1, 1 };
	static int[] dx = { 0, 1, -1, 1, -1, 0 };
	static int color[][], N, ans;
	static char[][] board;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		ans = 0;
		board = new char[N][N];
		color = new int[N][N];

		for (int i = 0; i < N; i++) {
			String str = br.readLine();
			for (int j = 0; j < N; j++) {
				board[i][j] = str.charAt(j);
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (board[i][j] == 'X' && color[i][j] == 0) {
					dfs(i, j, -1);
				}
			}
		}
		System.out.println(ans);
	}

	private static void dfs(int y, int x, int c) {
		color[y][x] = c;
		ans = Math.max(ans, 1);

		for (int d = 0; d < dy.length; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];

			if (ny < 0 || ny >= N || nx < 0 || nx >= N || board[ny][nx] == '-')
				continue;
			
			if(color[ny][nx] == 0) {
				ans = 2;
				dfs(ny, nx, -c); 
			}
			else if(color[ny][nx] == c) {
				System.out.println("3");
				System.exit(0);
			}
		}
	}
}