[백준 12946번] 육각 보드(JAVA)

문제

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

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

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

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 50)
둘째 줄부터 N개의 줄에는 어떤 칸을 색칠해야 하는지에 대한 정보가 주어진다.
i번째 줄의 j번째 문자는 (i, j)칸의 정보를 나타내고, '-'인 경우는 색칠하지 않는 것이고 'X'면 색칠해야 하는 것이다.

출력

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

---

정답

처음에는 육각보드를 너비탐색으로 풀었다. 근데 생각해보니 깊이 탐색이였다. 왜냐하면 X칸이 이어져있을때 주변의 색을 비교하면서 칠해야하는데 주변의 색을 비교하려면 주변에 색이 미리 채워져있어야했다. 주변의 색을 미리채우려면 깊이탐색으로 가장 마지막에 칠할 칸부터 칠하면서 비교해야 한다.

가장 중요한 포인트는 육각보드는 색 3개면 색을 채울수있다는 것이다. 굳이 6개 7개까지 필요하지 않다. 그리고 실제로 색을 칠하면서 코딩할 필요도 없다. 그져 색 칠하려는 칸 주변에 이미 칠해진 칸이 2개가 있다며 3가지 색을 칠해서 칠해야 한다. 이 부분에서 깊이탐색을 써야할 이유가 나온다.
만약 지도가
X X X
X X X
X X X
로 되어있다면 깊이탐색으로 탐색하는 순서는 (편의상 동쪽에서부터 시계방향으로 주변 칸을 탐색한다고 하자)
1 2 3
8 9 4
7 6 5
위와 같은 순서로 색을 칠하게 될것이다. 먼저 색이 "0","1" 2가지가 있다고 생각하고 두가지 색이 번갈아가면서 칠해진다고 생각하자

9번에 "0"을 칠하고 8번에 "1"을 칠한다. 그 다음 7번에 "0"을 칠하려고하는데 주변에 칠한색중 "0"이 있는지 없는지 확인해야한다. 9번이 "0"으로 칠해졌으므로 7번에는 제3의 색으로 칠해야 한다. 그러므로 이 육각지도는 그 이외의 색은 볼 필요도 없이 3개의 색의 사용해야한다.

이 문제는 육각노드를 칠하기 위해서 3개의 색만 필요하다는 것을 알고있는게 중요하다.(아니 근데 솔직히 이런 지식을 알고푸는것과 모르고 푸는거에서부터 차이가 난다.)

밑의 내가 푼 코드이다

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

public class Main {

    public static class Graph{
        char [][]map;
        int[] di = {-1,0,1,1,0,-1};
        int[] dj = {0,-1,-1,0,1,1};
        int[][] col;
        int ans;
        public Graph(int n) {
            map = new char[n][n];
            col = new int[n][n];
            for(int i =0;i<n;i++)
                for(int j=0;j<n;j++)
                    col[i][j] = -1;
            ans=0;
        }

        public void printUseColorCount() {
            System.out.println(ans);
        }
        public void addHexa(int index, String hexagon) {
            for(int i=0;i<hexagon.length();i++) {
                map[index][i] = hexagon.charAt(i);
            }
        }
        public void DFS(int i, int j, int c) {
            //col에 0 1 반복적으로 삽입
            col[i][j] = c;
            ans = ans>1 ? ans : 1;

            //주변 노드들 다 가져옴
            for(int x=0;x<6;x++) {
                int ni = i+di[x];
                int nj = j+dj[x];
                //범위 밖이면 패스
                if(!(ni>=0 && nj>=0 && ni<map.length && nj<map.length))
                    continue;
                //범위 안인데 X아니면 패스
                if(map[ni][nj] != 'X')
                    continue;
                //아직 칠하지 않은 칸이면 dfs실행
                if(col[ni][nj]==-1)
                    DFS(ni,nj,1-c);
                ans = ans<2 ? 2 : ans;
                //주변 색칠한 칸중에 내 c랑 값이 같으면 색 3개 이상 칠해야한다는 뜻
                if(col[ni][nj]==c)
                    ans  = ans<3 ? 3: ans;

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

        int n = Integer.parseInt(br.readLine());
        Graph g = new Graph(n);
        for(int i=0;i<n;i++) {
            String hexagon = br.readLine();
            g.addHexa(i, hexagon);
        }
        //깊이탐색
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (g.map[i][j] == 'X' && g.col[i][j] == -1)
                    g.DFS(i, j, 0);

        //사용한 색갯수 출력
        g.printUseColorCount();

        //g.showmap();


        br.close();
        bw.flush();
        bw.close();
    }
}

사실 이 문제는 도저히 못풀겠어서 다른 분의 코드를 참고했다. 생각해보니 내가 제대로 푼 문제가 아니였다. 그 분의 블로그도 참조해보길 바란다.

http://wookje.dance/2017/03/06/boj-12946-%EC%9C%A1%EA%B0%81-%EB%B3%B4%EB%93%9C/

[BOJ] 12946 : 육각 보드