[BOJ] 5373 큐빙 - Java

1. 문제 링크

https://www.acmicpc.net/problem/5373

 

---

2. 문제 풀이

 작년에 Java로 알고리즘을 본격적으로 시작하게 됐을 때 삼성 기출 위주로 스터디를 했습니다. 그때부터 눈여겨보던 문제였는데 A형 유형에 익숙해져서 구현 위주의 문제는 이제 마무리 지으려고 풀게 된 문제입니다. 구현이야 학부생부터 다른 언어 쓰면서도 다져온 것이니까 이제는 최적화를 중심으로 좀 더 심화된 알고리즘을 안 보고 코딩하는 연습을 해야겠습니다.

 

초기 전개도

 구현 쪽으로는 말이 좀 있는 문젠데 예전에 이 문제를 지나가면서 봤을 땐 배열만 어떻게 부분 복사만 하면 잘 될 거라 생각했습니다. 물론 풀진 않았지만. 전개도를 그리니까 삼성 기출에 들어있던 주사위 굴리기 문제가 생각났습니다. 풀면서 재밌었던 문제였는데 그때는 종이로 주사위를 만들고 굴려봤던 기억이 있네요.

 

주사위 굴리기

https://www.acmicpc.net/problem/14499

주사위 굴리기2

https://www.acmicpc.net/problem/23288

 

 큐빙도 이 문제 그대로는 좀 심심하니까 큐브 회전 + 큐브 굴리기 + 바닥면 복사 정도만 섞고?? n번의 굴리기 안에서 얻을 수 있는 특정 면의 최대 점수를 구하는 문제로 하나 만들면... ㅋ..

 

전개도 Mk2

 상(U), 전(F), 좌(L), 후(B), 우(R), 하(D) 순으로 번호를 넣어주었습니다. 이제 이 인덱스 번호를 기준으로 회전 명령이 들어왔을 때 바뀌는 위치들의 인덱스만 건들면 됩니다.

 

회전

 아, 그전에 큐브의 회전에 대해서 말해보자면 한 면을 4번 돌리면 그대로잖아요? 시계 방향으로 3번 돌리면? 반시계 방향으로 1번 돌린 것과 같습니다. 큐브를 돌릴 횟수가 최대 1000번이라 반시계 방향 대신 시계 방향으로 좀 더 돌린다고 TLE가 터지진 않습니다. 이러면 구현에 있어서도 코드의 양을 좀 더 줄일 수 있겠죠..?

 

    static char[] cube = new char[55];
    static void color() {
        char[] colorArr = new char[]{'w', 'r', 'g', 'o', 'b', 'y'};
        for(int i = 0; i < 6; i++)
            for(int j = 1; j <= 9; j++)
                cube[i*9+j] = colorArr[i];
    }

 음 그리고 이게 테스트 케이스 개수가 주어지니까 테케마다 초기 큐브 상태도 되돌려놔야 합니다. 불필요한 연산 줄이려고 생각하면서 작성한 건데 colorArr가 왜 저기에 있는 건지. 일단 푸는데 큰 문제가 되는 부분은 아니니 넘어갑시다. 이것과 관련해서 궁금한 게 생겨서 아래 코드를 돌려봤었습니다.

 

public class Main {
    public static void main(String[] args) {
        long beforeTime = System.currentTimeMillis();
        char[] arr = new char[1000];
        for(int i = 0; i < 10000000; i++) arr = new char[1000];
        long afterTime = System.currentTimeMillis();
        long secDiffTime = (afterTime - beforeTime)/1000;
        System.out.println("시간차이(m) : "+secDiffTime);

        beforeTime = System.currentTimeMillis();
        for(int j = 0; j < 10000000; j++)
            for(int i = 0; i < 1000; i++) arr[i] = '0';
        afterTime = System.currentTimeMillis();
        secDiffTime = (afterTime - beforeTime)/1000;
        System.out.println("시간차이(m) : "+secDiffTime);
    }
}

----
Result
시간차이(m) : 2
시간차이(m) : 0

Process finished with exit code 0

 당연한 것이긴 한데, 배열을 새로 할당하는 것보다 그냥 원래 있던 배열 요소만 새로 초기화하면 빠릅니다. Arrays.fill()을 해도 되구요. 저 '0'으로 초기화하는 반복문 부분이 사실상 Arrays.fill()이긴 합니다.

 

fill() 내부 코드

 

전개도 Mk3

 이제 남은 건 회전하기 전 원본 데이터를 들고 회전한 상태로 만들어주는 작업을 해야 합니다. 근데 전개도를 살짝 잘못 그렸습니다. 회전 후의 상태로 그려버려서..

 

전개도 Mk3.1

 구현할 땐 이렇게 종이를 돌리고 인덱스 번호를 맞춰주었습니다. 아래에 첨부한 상(U) 회전을 기준으로 설명하자면, 21개의 요소들을 저장할 배열을 선언한 후, 맨 위쪽 행부터 순서대로 저장합니다. 그 후에는 회전된 상태를 만들어야 하니까 -> 맨 오른쪽 열부터 위에서 아래로 채워나가면 됩니다. 참고로 한가운데 위치한 요소는 위치가 변하지 않으므로 저장해도 되고 안 해도 됩니다.

 

static void U(){
        char[] tmp = new char[21];
        tmp[0] = cube[34]; tmp[1] = cube[35]; tmp[2] = cube[36];
        tmp[3] = cube[21]; tmp[4] = cube[1]; tmp[5] = cube[2]; tmp[6] = cube[3]; tmp[7] = cube[37];
        tmp[8] = cube[24]; tmp[9] = cube[4]; tmp[10] = cube[5]; tmp[11] = cube[6]; tmp[12] = cube[40];
        tmp[13] = cube[27]; tmp[14] = cube[7]; tmp[15] = cube[8]; tmp[16] = cube[9]; tmp[17] = cube[43];
        tmp[18] = cube[10]; tmp[19] = cube[11]; tmp[20] = cube[12];

        cube[37] = tmp[0]; cube[40] = tmp[1]; cube[43] = tmp[2];
        cube[36] = tmp[3]; cube[3] = tmp[4]; cube[6] = tmp[5]; cube[9] = tmp[6]; cube[12] = tmp[7];
        cube[35] = tmp[8]; cube[2] = tmp[9]; /*cube[5] = tmp[10];*/ cube[8] = tmp[11]; cube[11] = tmp[12];
        cube[34] = tmp[13]; cube[1] = tmp[14]; cube[4] = tmp[15]; cube[7] = tmp[16]; cube[10] = tmp[17];
        cube[21] = tmp[18]; cube[24] = tmp[19]; cube[27] = tmp[20];
    }

 

회전 메서드들

 약간의 노가다 과정이 필요한데 펜과 종이만 있다면 생각보다 금방 합니다.

 

while(st.hasMoreTokens()) {
                String str = st.nextToken();
                char dir = str.charAt(0), clock = str.charAt(1);
                int cnt = 1;
                if(clock == '-') cnt = 3;
                for(int j = 0; j < cnt; j++) {
//                    System.out.println(dir + "방향 " + clock + " 시계");
                    switch(dir){
                        case 'U':
                            U();
                            break;
                        case 'D':
                            D();
                            break;
                        case 'F':
                            F();
                            break;
                        case 'B':
                            B();
                            break;
                        case 'L':
                            L();
                            break;
                        case 'R':
                            R();
                            break;
                    }
                }
//                System.out.println(Arrays.toString(cube));
            }

 이후에는 회전만 하다가 맨 윗면의 상태만 출력하면 해결되는 빡구현 문제입니다. 중간에 실수한 걸 찾기가 조금 힘들긴 할 텐데 큐브 돌릴 때처럼 U+ F+ F- U- 이런 식으로 돌렸다가 원상복구가 되는지 확인하면 됩니다. 원래대로 돌아오지 않는다면 그 회전 부분의 코드에 문제가 있는 겁니다.

뭔가 어려워요.

 

 배열을 돌리는 데 익숙하지가 않다? 그러면 배열 돌리기 시리즈로 연습하면 좋습니다. 이 문제들이랑 위에서 언급한 주사위 굴리기만 풀고 오면 금방 풀 수 있는 문제입니다.

 

배열 돌리기 1

https://www.acmicpc.net/problem/16926

배열 돌리기 2

https://www.acmicpc.net/problem/16927

배열 돌리기 3

https://www.acmicpc.net/problem/16935

배열 돌리기 4

https://www.acmicpc.net/problem/17406

 

---

3. 소스 코드

/***
 * start : ??
 * end : ??
 * elapsed : estimated 2h
 * @author madirony
 */
import java.io.*;
import java.util.*;
public class BOJ5373 {
    static int tc;
    static char[] cube = new char[55];
    static void color() {
        char[] colorArr = new char[]{'w', 'r', 'g', 'o', 'b', 'y'};
        for(int i = 0; i < 6; i++)
            for(int j = 1; j <= 9; j++)
                cube[i*9+j] = colorArr[i];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < tc; i++) {
            color();
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            while(st.hasMoreTokens()) {
                String str = st.nextToken();
                char dir = str.charAt(0), clock = str.charAt(1);
                int cnt = 1;
                if(clock == '-') cnt = 3;
                for(int j = 0; j < cnt; j++) {
//                    System.out.println(dir + "방향 " + clock + " 시계");
                    switch(dir){
                        case 'U':
                            U();
                            break;
                        case 'D':
                            D();
                            break;
                        case 'F':
                            F();
                            break;
                        case 'B':
                            B();
                            break;
                        case 'L':
                            L();
                            break;
                        case 'R':
                            R();
                            break;
                    }
                }
//                System.out.println(Arrays.toString(cube));
            }
            for(int j = 1; j <= 9; j++){
                sb.append(cube[j]);
                if(j%3 == 0) sb.append('\n');
            }
        }
        System.out.println(sb);
    }

    static void U(){
        char[] tmp = new char[21];
        tmp[0] = cube[34]; tmp[1] = cube[35]; tmp[2] = cube[36];
        tmp[3] = cube[21]; tmp[4] = cube[1]; tmp[5] = cube[2]; tmp[6] = cube[3]; tmp[7] = cube[37];
        tmp[8] = cube[24]; tmp[9] = cube[4]; tmp[10] = cube[5]; tmp[11] = cube[6]; tmp[12] = cube[40];
        tmp[13] = cube[27]; tmp[14] = cube[7]; tmp[15] = cube[8]; tmp[16] = cube[9]; tmp[17] = cube[43];
        tmp[18] = cube[10]; tmp[19] = cube[11]; tmp[20] = cube[12];

        cube[37] = tmp[0]; cube[40] = tmp[1]; cube[43] = tmp[2];
        cube[36] = tmp[3]; cube[3] = tmp[4]; cube[6] = tmp[5]; cube[9] = tmp[6]; cube[12] = tmp[7];
        cube[35] = tmp[8]; cube[2] = tmp[9]; /*cube[5] = tmp[10];*/ cube[8] = tmp[11]; cube[11] = tmp[12];
        cube[34] = tmp[13]; cube[1] = tmp[14]; cube[4] = tmp[15]; cube[7] = tmp[16]; cube[10] = tmp[17];
        cube[21] = tmp[18]; cube[24] = tmp[19]; cube[27] = tmp[20];
    }

    static void D(){
        char[] tmp = new char[21];
        tmp[0] = cube[30]; tmp[1] = cube[29]; tmp[2] = cube[28];
        tmp[3] = cube[39]; tmp[4] = cube[46]; tmp[5] = cube[47]; tmp[6] = cube[48]; tmp[7] = cube[19];
        tmp[8] = cube[42]; tmp[9] = cube[49]; tmp[10] = cube[50]; tmp[11] = cube[51]; tmp[12] = cube[22];
        tmp[13] = cube[45]; tmp[14] = cube[52]; tmp[15] = cube[53]; tmp[16] = cube[54]; tmp[17] = cube[25];
        tmp[18] = cube[18]; tmp[19] = cube[17]; tmp[20] = cube[16];

        cube[19] = tmp[0]; cube[22] = tmp[1]; cube[25] = tmp[2];
        cube[28] = tmp[3]; cube[48] = tmp[4]; cube[51] = tmp[5]; cube[54] = tmp[6]; cube[16] = tmp[7];
        cube[29] = tmp[8]; cube[47] = tmp[9]; /*cube[50] = tmp[10];*/ cube[53] = tmp[11]; cube[17] = tmp[12];
        cube[30] = tmp[13]; cube[46] = tmp[14]; cube[49] = tmp[15]; cube[52] = tmp[16]; cube[18] = tmp[17];
        cube[39] = tmp[18]; cube[42] = tmp[19]; cube[45] = tmp[20];
    }

    static void F(){
        char[] tmp = new char[21];
        tmp[0] = cube[7]; tmp[1] = cube[8]; tmp[2] = cube[9];
        tmp[3] = cube[27]; tmp[4] = cube[10]; tmp[5] = cube[11]; tmp[6] = cube[12]; tmp[7] = cube[43];
        tmp[8] = cube[26]; tmp[9] = cube[13]; tmp[10] = cube[14]; tmp[11] = cube[15]; tmp[12] = cube[44];
        tmp[13] = cube[25]; tmp[14] = cube[16]; tmp[15] = cube[17]; tmp[16] = cube[18]; tmp[17] = cube[45];
        tmp[18] = cube[54]; tmp[19] = cube[53]; tmp[20] = cube[52];

        cube[43] = tmp[0]; cube[44] = tmp[1]; cube[45] = tmp[2];
        cube[9] = tmp[3]; cube[12] = tmp[4]; cube[15] = tmp[5]; cube[18] = tmp[6]; cube[52] = tmp[7];
        cube[8] = tmp[8]; cube[11] = tmp[9]; /*cube[14] = tmp[10];*/ cube[17] = tmp[11]; cube[53] = tmp[12];
        cube[7] = tmp[13]; cube[10] = tmp[14]; cube[13] = tmp[15]; cube[16] = tmp[16]; cube[54] = tmp[17];
        cube[27] = tmp[18]; cube[26] = tmp[19]; cube[25] = tmp[20];
    }

    static void B(){
        char[] tmp = new char[21];
        tmp[0] = cube[48]; tmp[1] = cube[47]; tmp[2] = cube[46];
        tmp[3] = cube[19]; tmp[4] = cube[28]; tmp[5] = cube[29]; tmp[6] = cube[30]; tmp[7] = cube[39];
        tmp[8] = cube[20]; tmp[9] = cube[31]; tmp[10] = cube[32]; tmp[11] = cube[33]; tmp[12] = cube[38];
        tmp[13] = cube[21]; tmp[14] = cube[34]; tmp[15] = cube[35]; tmp[16] = cube[36]; tmp[17] = cube[37];
        tmp[18] = cube[1]; tmp[19] = cube[2]; tmp[20] = cube[3];

        cube[39] = tmp[0]; cube[38] = tmp[1]; cube[37] = tmp[2];
        cube[46] = tmp[3]; cube[30] = tmp[4]; cube[33] = tmp[5]; cube[36] = tmp[6]; cube[3] = tmp[7];
        cube[47] = tmp[8]; cube[29] = tmp[9]; /*cube[32] = tmp[10];*/ cube[35] = tmp[11]; cube[2] = tmp[12];
        cube[48] = tmp[13]; cube[28] = tmp[14]; cube[31] = tmp[15]; cube[34] = tmp[16]; cube[1] = tmp[17];
        cube[19] = tmp[18]; cube[20] = tmp[19]; cube[21] = tmp[20];
    }

    static void L(){
        char[] tmp = new char[21];
        tmp[0] = cube[28]; tmp[1] = cube[31]; tmp[2] = cube[34];
        tmp[3] = cube[48]; tmp[4] = cube[19]; tmp[5] = cube[20]; tmp[6] = cube[21]; tmp[7] = cube[1];
        tmp[8] = cube[51]; tmp[9] = cube[22]; tmp[10] = cube[23]; tmp[11] = cube[24]; tmp[12] = cube[4];
        tmp[13] = cube[54]; tmp[14] = cube[25]; tmp[15] = cube[26]; tmp[16] = cube[27]; tmp[17] = cube[7];
        tmp[18] = cube[16]; tmp[19] = cube[13]; tmp[20] = cube[10];

        cube[1] = tmp[0]; cube[4] = tmp[1]; cube[7] = tmp[2];
        cube[34] = tmp[3]; cube[21] = tmp[4]; cube[24] = tmp[5]; cube[27] = tmp[6]; cube[10] = tmp[7];
        cube[31] = tmp[8]; cube[20] = tmp[9]; /*cube[23] = tmp[10];*/ cube[26] = tmp[11]; cube[13] = tmp[12];
        cube[28] = tmp[13]; cube[19] = tmp[14]; cube[22] = tmp[15]; cube[25] = tmp[16]; cube[16] = tmp[17];
        cube[48] = tmp[18]; cube[51] = tmp[19]; cube[54] = tmp[20];
    }

    static void R(){
        char[] tmp = new char[21];
        tmp[0] = cube[36]; tmp[1] = cube[33]; tmp[2] = cube[30];
        tmp[3] = cube[3]; tmp[4] = cube[37]; tmp[5] = cube[38]; tmp[6] = cube[39]; tmp[7] = cube[46];
        tmp[8] = cube[6]; tmp[9] = cube[40]; tmp[10] = cube[41]; tmp[11] = cube[42]; tmp[12] = cube[49];
        tmp[13] = cube[9]; tmp[14] = cube[43]; tmp[15] = cube[44]; tmp[16] = cube[45]; tmp[17] = cube[52];
        tmp[18] = cube[12]; tmp[19] = cube[15]; tmp[20] = cube[18];

        cube[46] = tmp[0]; cube[49] = tmp[1]; cube[52] = tmp[2];
        cube[30] = tmp[3]; cube[39] = tmp[4]; cube[42] = tmp[5]; cube[45] = tmp[6]; cube[18] = tmp[7];
        cube[33] = tmp[8]; cube[38] = tmp[9]; /*cube[41] = tmp[10];*/ cube[44] = tmp[11]; cube[15] = tmp[12];
        cube[36] = tmp[13]; cube[37] = tmp[14]; cube[40] = tmp[15]; cube[43] = tmp[16]; cube[12] = tmp[17];
        cube[3] = tmp[18]; cube[6] = tmp[19]; cube[9] = tmp[20];
    }
}

---

4. 한줄평

 다른 알고리즘을 더 열심히 하자 . .