12946번 - 육각 보드

하우르·2021년 6월 17일
0

백준인강

목록 보기
26/30

문제

크기가 N × N인 육각 보드가 주어진다. 아래 그림은 N = 1, 2, 3, 4인 경우의 그림이다.

육각 보드의 일부 칸을 색칠하려고 한다. 두 칸이 변을 공유하는 경우에는 같은 색으로 칠할 수 없다.

어떤 칸을 색칠해야 하는지 주어졌을 때, 필요한 색의 최소 종류를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 50)

둘째 줄부터 N개의 줄에는 어떤 칸을 색칠해야 하는지에 대한 정보가 주어진다.

i번째 줄의 j번째 문자는 (i, j)칸의 정보를 나타내고, '-'인 경우는 색칠하지 않는 것이고 'X'면 색칠해야 하는 것이다.

출력

첫째 줄에 필요한 색의 종류의 최솟값을 출력한다.

예제 입력 1

3



예제 출력 1

0

예제 입력 2

4
-X--

---X

-X--

예제 출력 2

1

예제 입력 3

4
XXXX
---X
---X
---X

예제 출력 3

2

풀이

첫째 줄에 필요한 색의 종류의 최솟값을 출력한다. 이 것을 봤을때는 DFS로 풀어야하는게 아닐까 생각을 해본다.
1. N으로 2차원 배열 a 을 만들고
i번째 줄의 j번째 문자는 (i, j)칸의 정보를 배열에 저장한다.

2.또한 N으로 2차원 배열을 하나더 만든다. 색깔 정보를 담아둔다.

3.이제 배열 a를 0,0 부터돈다.
4. 이때 색칠해야하는 경우 재귀를 돈다.
5. (x,y)와 변을 공유하는 좌표는
- (x,y-1)
- (x,y+1)
- (x-1,y)
- (x-1,y+1)
- (x+1,y-1)
- (x+1,y)

6.범위가 넘어가는지 조건 체크
7.(x,y)와 변을 공유하는 좌표의 색상체크 여부가 X라면
8. 색상을 결정하는 방법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	final static int[] dx = { 0, 0, 1, -1, -1, 1 };
	final static int[] dy = { 1, -1, 0, 0, 1, 1 };
	static int n, ans;
	static int[][] color = new int[50][50];
	static int[][] check;
	static char[][] a;

	static void go(int x, int y, int c) {
		color[x][y] = c;
		ans = Math.max(ans, 1);
		for (int k = 0; k < 6; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (0 <= nx && nx < n && 0 <= ny && ny < n) {
				if (a[nx][ny] == 'X') {
					if (color[nx][ny] == -1) {
						go(nx, ny, 1 - c);
					}
					ans = Math.max(ans, 2);//X가 하나더있다면 정답은 2이거나 3이다
					if (color[nx][ny] == c) { //이미 방문한 경우인데 근데 색깔이 같다면 이분그래프가 아니므로 정답은 3이됨 
						ans = Math.max(ans, 3);
					}
				}
			}
		}

	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(reader.readLine());
		a = new char[n][n];
		color = new int[50][50];
		check = new int[n][n];
		for (int i = 0; i < n; i++) {
			StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
			a[i] = tokenizer.nextToken().toCharArray();
		}
		for (int i = 0; i < 50; i++) {
			Arrays.fill(color[i], -1);
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (a[i][j] == 'X' && color[i][j] == -1) {

					go(i, j, 0);
				}
			}
		}
		System.out.println(ans);
	}
}

결국 색상을 결정하는 부분에서 못했다ㅠ
강의 풀이로는
정답은 0,1,2,3 의 경우 밖에 없다.
0은 아무것도 색칠하지 않은 경우
1은 면이 닿아있지 않은 경우
2는 이분그래프인경우
3은 이분 그래프가 아닌경우

profile
주니어 개발자

0개의 댓글