[SPETIAL] Spatial Concepts Test

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/SPETIAL

algospot.com :: SPETIAL

 

풀이입니다. 🤔

 

import java.io.*;
 
public class Main {
    // [1] 이 (x - 1)이고, [1] 의 orientation 1 이 (y-1)일 때, [2] 의 Face 와 [1] 과 접촉 orientation
    private static final int[][][] ROTATIONS = new int[][][]{
            {{1, 0}, {4, 0}, {3, 0}, {2, 0}},
            {{4, 1}, {0, 3}, {2, 3}, {5, 3}},
            {{1, 1}, {0, 2}, {3, 3}, {5, 0}},
            {{2, 1}, {0, 1}, {4, 3}, {5, 1}},
            {{3, 1}, {0, 0}, {1, 3}, {5, 2}},
            {{1, 2}, {2, 2}, {3, 2}, {4, 2}}
    };
 
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        Face[] cube = new Face[6];
        Face[] answers = new Face[3];
        boolean[] ret = new boolean[5];
        int testCases = Integer.parseInt(reader.readLine());
        for (int testCase = 1; testCase <= testCases; ++testCase) {
            readFaces(cube, reader.readLine());
 
            int answerCount = 0;
            for (int i = 0, len = ret.length; i < len; ++i) {
                readFaces(answers, reader.readLine());
                ret[i] = isAnswer(cube, answers);
                if (ret[i]) ++answerCount;
            }
 
            System.out.printf("%d %d %c %c %c %c %c\n",
                    testCase,
                    answerCount,
                    getTrueOrFalse(ret[0]),
                    getTrueOrFalse(ret[1]),
                    getTrueOrFalse(ret[2]),
                    getTrueOrFalse(ret[3]),
                    getTrueOrFalse(ret[4])
            );
        }
    }
 
    private static void readFaces(Face[] buffer, String fold) {
        for (int i = 0, len = fold.length(); i < len; i+=2) {
            buffer[i / 2] = new Face(fold.charAt(i), fold.charAt(i + 1) - '1');
        }
    }
 
    private static boolean isAnswer(Face[] cube, Face[] answer) {
        boolean ret = false;
        for (int i = 0, faceLength = cube.length; i < faceLength && !ret; ++i) {
            // [1] 영역 검증 및 회전횟수 연산
            if (cube[i].shape != answer[0].shape) continue;
            // cube 의 orientation 과 answer 의 orientation 비교하여 [1] 의 1위치를 구한다.
            // f(cube, answer) = rotation
            // f(0, 0) = 0, f(0, 1) = 3, f(0, 2) = 2, f(0, 3) = 1
            // f(2, 2) = 0, f(2, 3) = 3, f(2, 0) = 2, f(2, 1) = 1
            int rotation = (4 + cube[i].orientation - answer[0].orientation) % 4;
 
            // [2] 영역 검증
            int[] right = ROTATIONS[i][rotation];
            if (cube[right[0]].shape != answer[1].shape) continue;
            if ((cube[right[0]].orientation - right[1] + 4) % 4 != answer[1].orientation) continue;
 
            // [3] 영역 검증
            int[] left = ROTATIONS[i][(rotation + 1) % 4];
            if (cube[left[0]].shape != answer[2].shape) continue;
            if ((cube[left[0]].orientation + 3 - left[1]) % 4 != answer[2].orientation) continue;
 
            // 모든 검증이 통과한다면, 정답 처리
            ret = true;
        }
 
        return ret;
    }
 
    private static char getTrueOrFalse(boolean ret) {
        return ret ? 'Y' : 'N';
    }
 
    private static final class Face {
        final char shape;
        final int orientation;
 
        public Face(char shape, int orientation) {
            this.shape = shape;
            this.orientation = orientation;
        }
    }
}

 

문제가 특별한 알고리즘 기술을 요구하는 것은 아니지만, 펼쳐진 직육면체에 대해 보여지는 단면을 나타내도록 하는 것이 쉽지 않았습니다. 
어려운 문제를 분리해서 각 단계마다 해결해나가는 것이 중요한 문제라 생각합니다. 

 

1. [1] 면에 대한 후보 탐색 및 회전 횟수 구하기

 

기준이 되는 [1] 면을 찾기 위해, 직육면체의 면(cube)들과 정답의 첫번째 면(answer[0])의 모양(shape)이 동일한 것을 탐색합니다. 

동일한 모양을 찾았다면, 현재의 회전 상태를 [1] 면의 1번을 기준으로 연산합니다. 

예를들어 Cube F3E4E2D3C2F3 가 입력이 되었을 때 예상되는 정답 C2D2F2 가 입력되었다면, 첫번째 정답 면 C2 의 모양 C 는 Cube 의 5번째 면 C2 와 동일하기 때문에 [1] 은 5번째 면이 됨을 알 수 있습니다. 

첫번째 예상되는 정답 면은 정위는 2, 5번째 면의 정위는 2 이기 때문에 현재 직육면체는 5번째 면의 1 을 기준으로 앞에 표시되고 있습니다. 
입력된 직육면체의 면이 3이고, 예상되는 정답의 면이 4이면 어떨까요?

시계방향으로 한번 회전했기 때문에 [1] 의 1 은 4를 기준으로 표시됩니다.

입력된 직육면체의 면이 3이고, 예상되는 정답의 면이 1이면 어떨까요?

시계방향으로 두번 회전했기 때문에 [1] 의 1 은 3를 기준으로 표시됩니다.

 

수학적 귀납법으로 직육면체 면의 정위가 x, 예상되는 정위가 y 라 할 때 [1] 의 1 은 어떤 기준으로 나타낼지 알아볼 수 있습니다.

이는 다음과 같은 식으로 정의 됩니다. 

 

f(x, y) = (4 + x - y) % 4

 

 

2. 회전 횟수에 근거하여, [2] 면에 대한 정보 검증 

 

앞에서, [1] 면의 후보와 표시되는 정위를 구할 수가 있었습니다. 

이를 바탕으로, [2] 면의 표시되는 정보를 알 수 있습니다. 
미리 선언한 배열 ROTATIONS 은 [1] 면이 x 이고 정위 1 이 y 로 표시될 때 [2] 면의 직육면체면의 번호와 x면과 접촉하는 정위입니다. 

예를들어 Cube F3E4E2D3C2F3 가 입력이 되었을 때 예상되는 정답 C2D2F2 가 입력되었고, [1]면이 5번째(C2), 정위 1을 기준으로 표시하고 있기 때문에 [2] 면은 4번째(D3)이며 5번째 면과 접촉된 정위는 2입니다.

 

ROTATIONS[4][0] = {3, 1}

 

배열에 존재하는 직육면체 번호를 이용하여 [2] 의 모양 검증 거친 후, [1] 과 접촉된 정위를 [2] 의 정위 1 이 되도록 회전시킵니다. 

앞의 예시에서 4번째 접촉면은 2 이며, [2] 의 1 은 2를 기준으로 표시하고 있습니다. 

 

 

3. 회전 횟수에 근거하여, [3] 면에 대한 정보 검증

 

마지막 단계는 서술된 2번의 단계와 유사합니다.

[3] 의 면은 [2] 의 면 옆에 있기 때문에 앞단계에서 선택된 ROTATIONS 의 다음이라 생각할 수 있습니다. 

예를들어 앞단계에서 ROTATIONS[4][0] 이 선택되었는데 [3] 면은 [2] 면의 옆에 있으니, ROTATIONS[4][1] 로 볼 수 있습니다.

 

이 후 단계는 서술된 2의 단계와 동일하지만, 표시하는 상단 기준이 1에서 4로 변경되었기 때문에 이 부분만 조금 변경하면 정답 검증을 해볼 수 있습니다. 

예를들어 Cube F3E4E2D3C2F3 가 입력이 되었을 때 예상되는 정답 C2D2F2 가 입력되었고, [1]면이 5번째(C2), 정위 1을 기준으로 표시하고 있고 때문에 [2] 면은 4번째(D3)이며 5번째 면과 접촉된 정위는 2일 때, [3]면은 1번째(F3)이며 5번째 면과 접촉된 정위는 1입니다.
접촉된 정위 1 을 [3] 의 4 를 기준으로 맞춰 검증해봅니다.

 

 

문제 해결을 위해 머릿속으로만 구상을 해보면, 쉽지가 않은 문제였습니다. 

A4 용지와 펜을 준비하여 직접 정육면체를 그려보고, 회전을 시켜보며 각각의 단계에 해당하는 요구사항을 만들어 일반화를 시킨다면, 충분히 이해하고 풀 수 있을 것이라 생각합니다. 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️