[백준 / BOJ] 1917 정육면체 전개도

문제

출처 : https://www.acmicpc.net/problem/1917

1917번: 정육면체 전개도

6*6크기의 그리드에 정육면체 전개도가 주어진다.

이 전개도를 조립했을때, 정육면체가 만들어지는지 구하는 문제다.

 

---

풀이

백트래킹을 이용한 구현 문제다.

 

문제를 자세히 생각해보면, 정육면체의 전개도의 모양은 중요하지않고, 색칠된 칸 끼리의 상대적 위치가 중요하다는것을 알수있다.

왜냐? 결국 정육면체가 만들어질 전개도라면, 초기 전개도의 모양에 상관없이 항상 정육면체가 만들어질것 이기 때문이다.

 

정육면체의 각 면에 다음과 같이 숫자를 적어놓자.

 

바닥면 : 1

천장면 : 6

오른쪽면 : 3

왼쪽면 : 5

아래쪽면 : 4

윗쪽면 : 2

 

다음으로 정육면체를 접었을때 연산을 구현해야한다.

(위 정육면체를 주사위라고 생각하고 구현하면된다.)

 

정육면체를 왼쪽으로 한번굴렸을때, 각 숫자들의 연관관계는 다음과 같다.

 

1 -> 2
2 -> 6
6 -> 3
3 -> 1

 

이를 4방향에 대해서 구현하면 된다.

 

소스코드

        private void doDown(){
            temp[1] = side[4];
            temp[4] = side[6];
            temp[5] = side[1];
            temp[6] = side[5];
            temp[2] = side[2];
            temp[3] = side[3];
        }
        
        private void doTop(){
            temp[1] = side[5];
            temp[4] = side[1];
            temp[5] = side[6];
            temp[6] = side[4];
            temp[2] = side[2];
            temp[3] = side[3];
        }
        
        private void doRight(){
            temp[1] = side[2];
            temp[2] = side[6];
            temp[3] = side[1];
            temp[6] = side[3];
            temp[4] = side[4];
            temp[5] = side[5];
        }
        
        private void doLeft(){
            temp[1] = side[3];
            temp[2] = side[1];
            temp[3] = side[6];
            temp[6] = side[2];
            temp[4] = side[4];
            temp[5] = side[5];
        }

 

정육면체의 전개도가 어떤식으로 주어질지 모르기 때문에, 가장처음 만나는 색칠된 칸을 바닥면(1번)으로 고정하고 위 연산을 진행하면 된다.

 

연산이 끝났을때, 항상 바닥면을 1번으로 고정해야함에 주의하자

 

주요 코드

    private void validateCubeOperate(int[][] arr, Cube cube, int y, int x){
        side++;
        cube.setCube(side);
        check[y][x] = true;
        for(int i = 1; i <= 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            if(outOfBounds(ny, nx) || check[ny][nx] || arr[ny][nx] == 0) continue;
            cube.changeSide(i); // 정방향
            validateCubeOperate(arr, cube, ny, nx);
            cube.changeSide(reverseDir[i]); // 역방향으로 되돌림
        }
    }

 

---

전체소스코드

https://github.com/devxb/JJUNalgo/blob/master/BOJ%20source%20code/1917%20%EC%A0%95%EC%9C%A1%EB%A9%B4%EC%B2%B4%20%EC%A0%84%EA%B0%9C%EB%8F%84/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃