[백준] code.plus(그래프 알고리즘,JAVA)12946번, 육각 보드

문제 링크

12946번: 육각 보드

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

그래프 알고리즘이란?

각 정점과 연결하는 선분의 정보를 가지고 BFS(너비 우선 탐색), DFS(깊이 우선 탐색) .... 등을 이용하여 정점에서 다른 정점으로 가는 최소값, 최대값 등의 문제에서 출력하라는 결과를 구하는 알고리즘입니다.

이 문제에 핵심은

1. 육각 보드에서 변을 마주하면 같은 색으로 칠할 수 없습니다.

2. '-'은 색을 채울 수 없는 칸, 'X'는 색을 채울 수 있는 칸입니다.

3. 색을 채울 수 있는 최소 종류를 결과로 출력합니다.

 

육각 보드에서 아래와 같은 형태일 때 채울 수 있는 색의 종류는 최대 3가지입니다.

아래와 같은 형태가 육각 보드를 색을 칠할 때 최대로 칠하는 것으로 육각 보드에 칠하는 색의 최대 종류는 3개입니다.

 

 

주어진 육각 보드의 정보를 가지고 색을 칠할 수 있는 칸에 DFS(깊이 우선 탐색)을 진행하여 색을 칠합니다.

 

만약 색을 칠한 종류가 3개이면 최대 종류를 칠했기 때문에 DFS탐색을 종료하고 3을 결과로 출력하였습니다.

 

 

예제입력3

'X'값인 곳(0,0)에서 DFS탐색을 시작합니다.

사용된 색의 종류는 2가지

2를 결과로 출력합니다.

 

DFS 탐색시

해당 칸 주변에 색을 비교하여 칠해지지 않은 색을 칠하였습니다.

(0, 0)은 주변에 아무 색이 없었기 때문에 빨간색으로 칠하였습니다.

(0, 1)은 주변에 빨간색이 있었기 때문에 다른색인 파란색을 칠하였습니다.

 

위 과정을 반복하여 'X'칸에 색을 칠하여 육각 보드를 완성하였습니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 각 'X'칸에 대하여 DFS탐색 및 색의 종류가 3개일 때 탐색 종료하는 search함수를 실행하였습니다.
• 색칠한 색의 종류의 개수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 각 'X'칸을 DFS로 탐색하였으며 색의 종류가 3개이면 더 이상 탐색을 하지 않고 종료합니다.
• dfs함수는 DFS로 탐색하여 주변에 칠해지지 않은 색깔을 칠한 인접한 'X'을 탐색합니다.

 

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

public class Main{
	static int N,result = 0;
	static char[][] board;		//육각 보드 정보 배열
	static int[] dx = {0, 1, -1, 1, -1, 0};		//육각보드 주변 탐색을 위한 X값 변경값
	static int[] dy = {-1, -1, 0, 0, 1, 1};		//육각보드 주변 탐색을 위한 y값 변경값
	static int[][] tempBoard;		//육각 보드에 무슨 색이 칠해졌는데 저장하는 배열
	static boolean[][] visited;		//육각 보드 칸 방문 저장 배열
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		N = Integer.parseInt(br.readLine());
		board = new char[N][N];
		tempBoard = new int[N][N];
		visited = new boolean[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);
			}
		}
		search();		//DFS 탐색 시작을 위한 함수 실행
		bw.write(result + "\n");		//색칠한 색 종류 BufferedWriter 저장
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//보드 'X'칸 DFS탐색 및 색 종류 3개일 때 DFS 탐색 종료
	static void search() {
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if(board[i][j] == 'X' && !visited[i][j])	//'X'칸 DFS 탐색 시작
					dfs(j,i);
				if(result==3)	//색 종류 3개, DFS 탐색 종료
					return;
			}
		}
	}
    	//DFS 탐색으로 색을 칠하는 함수
	static void dfs(int x, int y) {
		if(result == 3)		//색칠한 색의 종류가 3개일 때 종료
			return;
		boolean[] color = new boolean[4];	//색 관련 배열
		visited[y][x] = true;	//해당 칸 방문 확인
		for(int i=0;i<6;i++) {
			int tempX = x + dx[i];		//X값 변경
			int tempY = y + dy[i];		//Y값 변경
            	//해당 칸 근처 색칠에 사용된 색 확인
			if(tempX>=0 && tempY>=0 && tempX<N && tempY<N) {
				if(board[tempY][tempX] == 'X' && tempBoard[tempY][tempX]!=0) 
					color[tempBoard[tempY][tempX]] = true;
			}
		}
        	//주변 사용된 색 제외한 현재 칸 색칠하기
		for(int i=1;i<color.length;i++) {
			if(!color[i]) {
				result = Math.max(result, i);
				tempBoard[y][x] = i;
				break;
			}
		}
        	//DFS로 인접한 'X'칸으로 이동
		for(int i=0;i<6;i++) {
			int tempX = x + dx[i];
			int tempY = y + dy[i];
			if(tempX>=0 && tempY>=0 && tempX<N && tempY<N) {
				if(board[tempY][tempX] == 'X' && !visited[tempY][tempX]) 
					dfs(tempX,tempY);
			}
		}
	}
}