백준 5373번 큐빙 문제 풀이 (자바)

백준 5373번 큐빙 문제 풀이 (JAVA)

https://boj.kr/5373

/*
 * Author : aahcbird
 * Blog   : aahc.tistory.com
 * Created: 2019.03.02
 */
import java.io.*;
import java.util.*;
 
 
 
class Main {
    static final int U = 0, D = 1, F = 2, B = 3, L = 4, R = 5;
    static InputReader in;
    static PrintWriter out;
    
    int T, n;
    char[][][] cube;
    
    void init(char[] colors) {
        int num = colors.length;
        cube = new char[num][][];
        
        for (int i=0; i<num; ++i) {
            cube[i] = new char[3][3];
            for (int j=0; j<3; ++j)
                for (int k=0; k<3; ++k)
                    cube[i][j][k] = colors[i];
        }
    }
    
    void alter(int f, int u, int l, int d, int r, boolean clk) {
        char[][] tmp = new char[3][3];
        char[] tmp2 = new char[3];
        
        if (clk) {
            for (int i=0; i<3; ++i)
                for (int j=0; j<3; ++j) {
                    tmp[i][j] = cube[f][2-j][i];
                }
            for (int i=0; i<3; ++i)
                tmp2[i] = cube[u][i][0];
            for (int i=0; i<3; ++i)
                cube[u][i][0] = cube[l][0][2-i];
            for (int i=0; i<3; ++i)
                cube[l][0][2-i] = cube[d][2][i];
            for (int i=0; i<3; ++i)
                cube[d][2][i] = cube[r][2-i][2];
            for (int i=0; i<3; ++i)
                cube[r][2-i][2] = tmp2[i];
        }
        else {
            for (int i=0; i<3; ++i)
                for (int j=0; j<3; ++j) {
                    tmp[i][j] = cube[f][j][2-i];
                }
            for (int i=0; i<3; ++i)
                tmp2[i] = cube[u][i][0];
            for (int i=0; i<3; ++i)
                cube[u][i][0] = cube[r][2-i][2];
            for (int i=0; i<3; ++i)
                cube[r][2-i][2] = cube[d][2][i];
            for (int i=0; i<3; ++i)
                cube[d][2][i] = cube[l][0][2-i];
            for (int i=0; i<3; ++i)
                cube[l][0][2-i] = tmp2[i];
        }
        cube[f] = tmp;
    }
    
    void rotate(String str) {
        boolean clk = str.charAt(1) == '+';
        
        switch (str.charAt(0)) {
        case 'U': alter(U, L, F, R, B, clk); break;
        case 'D': alter(D, B, R, F, L, clk); break;
        case 'F': alter(F, U, L, D, R, clk); break;
        case 'B': alter(B, R, D, L, U, clk); break;
        case 'L': alter(L, F, U, B, D, clk); break;
        case 'R': alter(R, D, B, U, F, clk); break;
        }
    }
    
    void printU() {
        for (int i=0; i<3; ++i) {
            for (int j=0; j<3; ++j)
                out.print(cube[0][j][2-i]);
            out.println();
        }
    }
    
    void solve() {
        T = in.nextInt();
        while (T-->0) {
            init(new char[]{'w','y','r','o','g','b'});
            n = in.nextInt();
            while (n-->0) {
                rotate(in.nextStr());
            }
            printU();
        }
    }
    
    public static void main(String[] args) {
        in = new InputReader(System.in);
        out = new PrintWriter(System.out);
        new Main().solve();
        out.close();
    }
    
    static class InputReader {
        BufferedReader br;
        StringTokenizer st;
        
        public InputReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        
        public String nextStr() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        
        public int nextInt() {
            return Integer.parseInt(nextStr());
        }
    }
}
 

풀이 과정

init() - 큐브를 3차원 배열의 형태로 생성하고, 각 면을 주어진 색상으로 칠해 초기화하는 메서드

rotate() - 큐브를 돌리기위해 입력값에 따라 alter() 메서드를 호출하는 몸통 메서드

alter() - 큐브를 돌릴 때 바라보는 면과 그 면에 접한 면들의 정보, 그리고 돌리는 방향이 주어졌을 때 큐브를 돌리는 메서드

printU() - 큐브의 윗 부분을 뒷면과 접한 방향부터 차례로 출력하는 메서드

init() 메서드에 char 배열 {'w','y','r','o','g','b'}을 넘겨준다.

이 배열을 매개변수로 넘겨받은 init() 메서드는 큐브의 6개 면(각각 3x3칸)을 위, 아래, 앞, 뒤, 왼쪽, 오른쪽 순서로 흰색, 노란색, 빨간색, 오렌지색, 초록색, 파란색으로 초기화 해준다.

초기화를 완료한 후에 '돌리는 면과 돌리는 방향' 입력을 받아 StringTokenizer로 쪼갠 후 rotate() 메서드에 String형의 매개변수로 전달해준다.

rotate 메서드는 입력 받은 String형 매개변수 str의 값에 따라 alter() 메서드를 호출한다.

alter() 메서드는 (돌려야 될 면, 돌려야 될 면의 윗부분에 접한 면, 왼쪽, 아래, 오른쪽, 돌리는 방향) 의 형식으로 매개변수를 받는다.

참고

이런 식으로 alter() 메서드를 호출하면서 같이 건네주는 매개변수만 바꿔서 큐브를 회전하는 코드를 구현하는 것은 그리 간단하지 않다.

아무 생각없이 각각의 면 6개과 2개의 방향에 대한 코드를 작성한다면 rotate() 메서드와 alter() 메서드로 끝나는 것이 아닌, alter() 메서드의 6배의 길이에 해당하는 코드를 타이핑하고, 정당성을 일일히 검증해야 한다. 이는 단순한 복사 붙여넣기 작업이 아니므로 그 만큼 시간이 더 걸릴 것이다.

모듈화를 통해 코드의 재사용성을 높일 수 있는 상황에서 그렇게 길고 단순무식한 코드를 작성하는 것은 적절하지 못하다.

내가 보고 있는 방향이 앞이건, 뒤건, 왼쪽이건, 아래 방향이건 상관없이 alter() 메서드를 호출했을 때 alter()가 비슷한 입력에 대해 같은 용도로 쓰이기 위해서는 큐브의 어느 방향을 기준으로 보더라도 보고 있는 면과 그 면을 기준으로 하는 나머지 5개의 면(위, 아래, 뒤, 왼쪽, 오른쪽)을 구현한 2차원 배열의 작성 방향이 동일해야 한다.

ex) {'앞면', '2차원 배열이 아래쪽으로 작성됨'} 인 면을 기준으로 바라볼 때 보이는 나머지 5개의 면의 2차원 배열 작성 방향이 {'왼쪽면', '2차원 배열이 아래쪽으로 작성됨'} 인 면을 기준으로 바라볼 때 보이는 나머지 5개의 면의 2차원 배열 작성 방향과 같고,

{'뒷면', '2차원 배열이 오른쪽으로 작성됨'} 인 면을 기준으로 바라볼 때 보이는 나머지 5개의 면의 2차원 배열 작성 방향이 {'아래쪽면', '2차원 배열이 오른쪽으로 작성됨'} 인 면을 기준으로 바라볼 때 보이는 나머지 5개의 면의 2차원 배열 작성 방향과 같다.

이렇게 큐브의 6개 면이 '표준화'된 형태로 각 면의 2차원 배열의 작성 방향을 나타내는 방법은 4개가 있다.

다음은 {위, 아래, 앞, 뒤, 왼, 오른} 면의 순서대로 2차원 배열이 써내려간 방향을 표기한 4개의 큐브 표준화 케이스이다.

1. {오른, 뒤, 위, 왼, 아래, 앞}

2. {왼, 앞, 아래, 오른, 위, 뒤}

3. {왼, 뒤, 위, 오른, 앞, 아래}

4. {오른, 앞, 아래, 왼, 뒤, 위}

(*관측자 기준)

정육면체를 그린 후에 {위, 아래, 앞, 뒤, 왼, 오른} 면에 위에 적은 각각의 케이스를 순서대로 화살표를 그려가며 생각하면 이해가 쉬울 것이다.

나는 4번 케이스를 기준으로 코드를 구현했다.

큐브를 돌리는 코드는 rotate()와 alter()에 있는데, 둘 다 상수시간 안에 수행 가능하므로 시간 복잡도는 큐브를 돌리는 입력의 개수와 동일한 O(N)이고,

큐브에 대한 정보는 면의 색상에 대한 것만 메모리에 저장하면 되니 O(1)의 공간복잡도를 가짐을 알 수 있다.