백준 16939 문제이다.
Java로 풀이했다.
참고로 이 문제는 굉장히 좋은 문제이다.
문제 자체의 퀄리티가 굉장히 좋다.
문제가 깔끔하고 실력 향상에도 많은 도움이 된다.
예전에 한번 풀려고 시도했지만 당시에 답안에 거의 근접했는데 사소한 로직에서 실수를 해서 풀지 못했다.
대략적인 풀이방법은 알고있었지만 오늘에서야 해당 로직을 수정하게 되었다.
구현 문제이고 정말 흥미로운 문제이다. 개인적으로 이런 문제를 좋아한다.
어째서인지 복잡한 구현 문제가 가장 재미있다.
그리고 참고로 이 문제는 도전 정신을 자극했다.
풀릴것같으면서도 풀리지 않아서 오히려 그렇게 느낀 것 같다.
28일전에 풀려고 했다가 다시 2주전에 시도했다가 오늘에서야 완벽하게 풀었다.
아래에서 솔루션을 설명하도록 하겠다.
코드가 꽤 길기 때문에 차근차근 읽고나면 친절하게 설명하도록 하겠다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int[][] cubeMatrix = new int[6][8];
public static int[][] cubeIndex =
{
{0, 2}, {0, 3}, {1, 2}, {1, 3},
{2, 2},{2, 3}, {3, 2}, {3, 3},
{4, 2}, {4, 3}, {5, 2}, {5, 3},
{2, 0}, {2, 1}, {3, 0}, {3, 1},
{2, 4}, {2, 5}, {3, 4}, {3, 5},
{2, 6}, {2, 7}, {3, 6}, {3, 7}
};
public static int[][][] matrixPlane = {
{{0, 2}, {0, 3}, {1, 2}, {1, 3}},
{{2, 2}, {2, 3}, {3, 2}, {3, 3}},
{{4, 2}, {4, 3}, {5, 2}, {5, 3}},
{{2, 0}, {2, 1}, {3, 0}, {3, 1}},
{{2, 4}, {2, 5}, {3, 4}, {3, 5}},
{{2, 6}, {2, 7}, {3, 6}, {3, 7}}
};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < 24; i++){
int[] position = cubeIndex[i];
int colorNumber = Integer.parseInt(st.nextToken());
cubeMatrix[position[0]][position[1]] = colorNumber;
}
int[][] movement = {
{1, 3, 5, 7, 9, 11, 24, 22},
{2, 4, 6, 8, 10, 12, 23, 21},
{13, 14, 5, 6, 17, 18, 21, 22},
{15, 16, 7, 8, 19, 20, 23, 24},
{3, 4, 17, 19, 10, 9, 16, 14},
{1, 2, 18, 20, 12, 11, 15, 13}
};
boolean result = false;
for(int i = 0; i < 6; i++){
result = rotateCube(movement[i]);
if(result){
break;
}
}
if(result){
System.out.println("1");
}else {
System.out.println("0");
}
}
public static int[][] deepCopy(int[][] original) {
int[][] result = new int[6][8];
for(int i = 0; i < 6; i++){
System.arraycopy(original[i], 0, result[i], 0, 8);
}
return result;
}
public static boolean rotateCube(int[] movement){
// forward rotation
Deque<Integer> forwardDeque = new LinkedList<>();
for(int j = 0; j < 8; j++){
int[] position = cubeIndex[movement[j] - 1];
forwardDeque.add(cubeMatrix[position[0]][position[1]]);
}
int val1 = forwardDeque.pollFirst();
forwardDeque.addLast(val1);
int val2 = forwardDeque.pollFirst();
forwardDeque.addLast(val2);
int[][] copiedForwardArr = deepCopy(cubeMatrix);
for(int i = 0; i < 8; i++){
int[] position = cubeIndex[movement[i] - 1];
copiedForwardArr[position[0]][position[1]] = forwardDeque.poll();
}
if(isSolved(copiedForwardArr)){
return true;
}
// backward rotation
Deque<Integer> backwardDeque = new LinkedList<>();
for(int j = 0; j < 8; j++){
int[] position = cubeIndex[movement[j] - 1];
backwardDeque.add(cubeMatrix[position[0]][position[1]]);
}
int val11 = backwardDeque.removeLast();
backwardDeque.addFirst(val11);
int val22 = backwardDeque.removeLast();
backwardDeque.addFirst(val22);
int[][] copiedBackwardArr = deepCopy(cubeMatrix);
for(int i = 0; i < 8; i++){
int[] position = cubeIndex[movement[i] - 1];
copiedBackwardArr[position[0]][position[1]] = backwardDeque.poll();
}
return isSolved(copiedBackwardArr);
}
public static boolean isSolved(int[][] receiveCubeMatrix){
for(int i = 0; i < 6; i++) {
int a = receiveCubeMatrix[matrixPlane[i][0][0]][matrixPlane[i][0][1]];
int b = receiveCubeMatrix[matrixPlane[i][1][0]][matrixPlane[i][1][1]];
int c = receiveCubeMatrix[matrixPlane[i][2][0]][matrixPlane[i][2][1]];
int d = receiveCubeMatrix[matrixPlane[i][3][0]][matrixPlane[i][3][1]];
if(!(((a == b) && (b == c)) && (c == d))){
return false;
}
}
return true;
}
}
문제에서 큐브를 펼쳐놓은 것 같은 그림이 주어진다.
바로 아래처럼 말이다.
자 그렇다면 이 큐브를 표현하기 위해서 우린 이 큐브를 어떻게 추상화할 수 있을까?
위 사진에서 가로의 최대 길이는 8이다. 그리고 세로의 최대길이는 6이다.
그렇다면 정확히 이 사이즈만큼의 이중배열이 존재한다고 가정할 수 있지 않을까? (불필요한 모서리 부분은 그냥 안써도 괜찮으니 말이다. 우리가 필요한 부분 즉 큐브를 펼쳐놓은 부분만 접근해서 사용하면 되지 않을까?)
그렇게 해서 탄생한 것이 static 변수인 cubeMatrix이다. (이 이중배열에 우리는 우리가 받게될 실질적인 값을 할당할 예정이다.)
모서리쪽에 해당하는 귀퉁이쪽은 어차피 쓰지도 않는 공간이니 우리가 신경쓸 곳은 큐브를 펼쳤을때의 모양과 겹치는 곳이다. 그곳만 신경쓰면 된다.
그리고 이어서 cubeIndex 가 나온다.
지금 그림을 보면 큐브를 펼쳤을때의 각 면에 대하여 번호가 매겨진 것을 확인할 수 있는데 1~24까지 매겨져 있다.
그리고 cubeIndex 는 위에서 선언한 cubeMatrix 에서 해당 1~24의 위치에 해당되는 row index와 col index를 의미한다고 보면 된다. (실제 배열상의 위치를 표현한 것이다.) 물론 cubeIndex는 배열의 index 0부터 시작하지만 실제 큐브 상에 표시된 수는 범위가 1부터 시작하기 때문에 로직의 어느 순간에서는 우리는 -1 을 적용해줘야함을 알 수 있다. (맞춰주기 위함이다. 이 부분은 개인 취향인데 나는 앞에 0번째 인덱스를 비워두는게 싫어서 이렇게 만든거다. 만약 진짜 깔끔하게 접근하고 싶은 사람은 인덱스 0을 비워두고 1부터 값을 채워놓은 상태로 시작하면 -1을 하지 않고도 그대로 접근할 수 있어서 가독성이 좋을 것이다.)
main에서는 BufferedReader 를 활용해 일반 문제들처럼 입력을 받아준다.
그리고 for문을 24번 동안 looping 할건데 그 이유는 우리가 24개의 number를 받을 것이고 해당 number 는 cube의 각 영역에 대입할 실제 값 즉 value이기 때문이다.
아래 코드가 그 이유때문에 존재한다. 실제 이중배열인 cubeMatrix의 해당 위치에 대해 외부로부터 전달받은 값을 넣어준다.
그리고 그 값이 할당되는 위치는 cubeIndex에서 알고 있으므로 해당 cubeIndex에서 가져온 값을 int[] 인 position 으로 잡아서 그 값의 position[0]으로 row index와 position[1]로 col index에 접근하는 것이다. 그러니 cubeMatrix 의 정확한 위치에 전달받은 값을 집어넣을 수 있다.
for(int i = 0; i < 24; i++){
int[] position = cubeIndex[i];
int colorNumber = Integer.parseInt(st.nextToken());
cubeMatrix[position[0]][position[1]] = colorNumber;
}
여기까지 진행하면 우리는 일단은 기본적으로 입력받은 값들에 대해서 해당 큐브의 정확한 위치에 맞게 집어넣어주었다. 당연히 큐브의 영역에 해당되지 않는 곳은 그저 비어있을 것이다.
이제 큐브를 돌리기만 하면 된다.
어느 축을 기준으로 큐브를 돌릴까?
다행히도 문제는 2x2x2 사이즈로 굉장히 작은 큐브이다. 즉 축 정보를 우리가 직접 명시할 수 있을 정도의 큐브이다.
(한마디로 돌릴 수 있는게 별로 많지가 않다. 3x3x3 만 되었어도 꽤 복잡했을 것이다.)
그래서 우리는 movement라는 int[][] 를 선언해줬다.
이게 무슨 의미인지 알아보자.
1 3 5 7 9 11 24 22 는 뭘 의미할까?
간단하게만 알아보겠다.
아래 그림을 보면 바로 이해가 갈 수 있다.
즉 우리가 돌리고자 하는 하나의 축의 정보를 의미한다. 이 축의 숫자를 기록해놓은 것이다. (24와 22는 뭐죠? 라는 생각이 든다면 위의 그림을 종이처럼 다시 접어서 정육면체의 입체 큐브로 만든다고 생각하면 된다. 그러면 24와 22가 결국은 5와 7의 천장에 해당한다고 여길 수 있다. )
나머지 배열들도 마찬가지다.
마찬가지로 다른 축들에 대한 정보를 담고 있다.
그리고 나면 총 6개의 축에 대해서 큐브를 돌릴 수 있음을 알게 된다. (왜 여섯개인지는 직접 세보았기 때문에 안다.)
그러면 이제 for문에서 6번을 돌면서 rotateCube를 호출하면서 한번만에 큐브를 맞출 수 있는지 체크하자.
물론 결과로 받은 boolean 변수인 result가 true 이면 바로 맞추는게 가능하니 곧바로 break 하고 나가서 1을 출력하고 끝내자.
이제 rotateCube메서드를 알아볼 차례이다.
어떻게 보면 이 코드가 문제의 핵심이다.
그러니 다시 한번 코드를 천천히 살펴보고 설명을 진행하겠다.
public static boolean rotateCube(int[] movement){
// forward rotation
Deque<Integer> forwardDeque = new LinkedList<>();
for(int j = 0; j < 8; j++){
int[] position = cubeIndex[movement[j] - 1];
forwardDeque.add(cubeMatrix[position[0]][position[1]]);
}
int val1 = forwardDeque.pollFirst();
forwardDeque.addLast(val1);
int val2 = forwardDeque.pollFirst();
forwardDeque.addLast(val2);
int[][] copiedForwardArr = deepCopy(cubeMatrix);
for(int i = 0; i < 8; i++){
int[] position = cubeIndex[movement[i] - 1];
copiedForwardArr[position[0]][position[1]] = forwardDeque.poll();
}
if(isSolved(copiedForwardArr)){
return true;
}
// backward rotation
Deque<Integer> backwardDeque = new LinkedList<>();
for(int j = 0; j < 8; j++){
int[] position = cubeIndex[movement[j] - 1];
backwardDeque.add(cubeMatrix[position[0]][position[1]]);
}
int val11 = backwardDeque.removeLast();
backwardDeque.addFirst(val11);
int val22 = backwardDeque.removeLast();
backwardDeque.addFirst(val22);
int[][] copiedBackwardArr = deepCopy(cubeMatrix);
for(int i = 0; i < 8; i++){
int[] position = cubeIndex[movement[i] - 1];
copiedBackwardArr[position[0]][position[1]] = backwardDeque.poll();
}
return isSolved(copiedBackwardArr);
}
우리는 큐브의 하나의 축에 대한 정보인 movement 를 받았다.
그렇다면 해당 축을 꼭 한방향으로만 돌리란 법이 있을까?
forward로도 돌릴 수 있고 backward로도 돌릴 수 있다.
그러니 대충 어떤 로직이든 간에 두번 처리해야함을 알 수 있다.
한 축의 정보는 위에서 예시로 든 것처럼 1 3 5 7 9 11 24 22 가 될 수 있다.
우리가 rotateCube에서 수행할 로직은 이 축에 대해서 딱 한번씩만 앞 뒤로 돌려볼 것이다. 그러니 앞쪽으로 한번 돌리면 이 축 정보가 5 7 9 11 24 22 1 3 이 되겠고 뒤쪽으로 돌리면 24 22 1 3 5 7 9 11 이 될 것이다. (사실 정확히 어느 방향이 앞이냐 뒤냐는 내 기준이 어디냐에 따라서 다르기 때문에 앞이냐 뒤냐는 크게 상관쓰지말고 두 방향으로 한번씩은 돌려야함을 인지하면 된다.)
그런데 지금 돌리는 모습을 보자니 딱 어떤 자료구조가 적합하겠다는 생각이 떠오른다.
stack은 아쉽고 queue 까지 떠올렸다면 성공이다.
우리는 deque 를 사용할 것이다.
우선 forwardDeque에 기존에 갖고 있던 축의 정보를 넣어준다.
그리고 forwardDeque 에서 앞에서 하나를 빼고 그걸 다시 addLast를 통해서 뒤에 넣어준다.
또 한번 빼서 또 뒤에 넣어주는걸 한번 더 한다. (이게 바로 축을 돌리는 과정이다. 큐브가 돌아가는 모습을 상상해봐라.)
그리고 deepcopy를 하는데 원본 cube 를 훼손하고 싶지 않기 때문이다. 복사해서 체크할 생각이다. (이건 기본수칙)
copy된 cube에 대해서 이제 deque에 있는 정보를 쭉 밀어넣어주자. 즉 축의 정보를 한번 돌린 정보로 갱신해주는 셈이다.
이제 체크해야하니까 돌린 정보를 큐브안에 넣어주는거다.
여기까지 됬으면 이제 이 cube가 맞춰진건지 확인해줘야한다. 그러니 isSolved를 통해서 체크해준다.
isSolved는 상당히 간단한 메서드이다.
먼저 알아야할 사항이 있다.
matrixPlane이라는 int[][] 변수가 정의되어있는데 이것은 큐브에 존재하는 여섯 개의 면에 대해서 그것이 실제 이중배열에서의 row index, col index 가 어떻게 되는지 즉 실제 위치를 정의한 변수이다.
matrixPlane의 첫번째 요소는 다음과 같다.
{{0, 2}, {0, 3}, {1, 2}, {1, 3}}
이 정보가 큐브 상에서 어느 곳을 표현하고 있는지 그림을 통해 알아보면 아래와 같다.
헷갈리면 직접 6x8 사이즈의 이중배열 상에서의 location 을 따져보면 된다.
isSolved 메서드에서는 그렇게 matrixPlane 을 활용해서 한 분면의 4개의 영역에 대한 값을 각각 a,b,c,d 로 받아낸다.
그리고 이제 우리가 확인할 건 이 4개의 값이 모두 동일한지 체크하면 된다.
체크하고 난뒤 해당 여부를 boolean 값을 통해 리턴한다.
isSolved 를 통해 foward rotation에 대해서 참 여부를 판별했으면 backward rotation 에 대해서도 forward와 비슷한 로직을 수행하면 된다. (다만 deque 의 어디에서 빼고 어디로 다시 집어넣는지는 방금 전과 반대임을 잊으면 안된다.)
그렇게 수행하면 문제가 해결된다.
여기까지가 문제의 설명이다.
설명이 부족했을텐데 다른 트릭이 있는 문제가 아니라 순수하게 구현 문제이기 때문에 직접 배열에 선언된 값들을 따라가면서 이해하는 것이 좋다.
참고로 1등 솔루션 중에 나처럼 deque에 해당 축 정보를 밀어넣는게 아니라 그냥 직접 축을 돌리는 과정을 하드코딩으로 직접 박아넣어서 속도를 줄이신 분이 계신다. 어떻게 보면 구현 문제이다보니 그게 맞는 방법이라는 생각이 들기도 하는데 직관적이냐 아니냐를 따져본다면 내 코드가 좀 더 직관적이라는 생각이 든다.
큐브를 돌리는 과정이 코드 상에서 추상화되어 드러나있다는 점에서 그렇게 생각한다.
한달전부터 시간날때마다 조금씩 풀어보려했던 문제인데 오늘 풀어서 꽤나 기분이 좋다.
이런 유형의 문제는 실력 향상에 굉장한 도움이 된다.
이해되지 않는 부분이 있다면 언제든 댓글로 남겨주시기 바랍니다.
'Algorithm > 문제풀이' 카테고리의 다른 글
| [leetcode] 2451. Odd String Difference - Rust (1) | 2024.05.03 |
|---|---|
| [leetcode] 1417. Reformat The String - cpp (0) | 2024.05.01 |
| [BOJ] 백준 2529 부등호 - Java 풀이 (0) | 2022.10.12 |
| [BOJ] 백준 16953 A → B - Python3 풀이 (0) | 2022.09.16 |
| [LeetCode] LeetCode 1576. Replace All ?'s to Avoid Consecutive Repeating Characters - python3 (0) | 2022.09.14 |