티어: 플1
나는 MITM를 사용하지 않았기 때문에 MITM을 사용한 풀이를 다루지 않는다.
이 문제를 풀 때 가장 주의해야할 점이라면 2x2x2 큐브의 색 배치가 우리가 아는 색이 아닐수도 있다는 것이다.
원래 큐브의 마주보는 면 색 배치는 흰-노, 파-초, 빨-주 쌍을 이루지만, 예제에서 주어지는 큐브 전개도만 보아도 흰색과 노란색이 한 조각에 있는것을 알 수 있다. 문제를 풀기 전에 마주보는 면 색 배치에 대한 처리가 필요하다.
그리고, 큐브의 제일 뒤 아래 조각이 고정된 상태로 움직여야 한다는 점에서, 흰색을 밑면으로 하고 노란색을 윗면으로 하는 기본적인 큐브 맞추기를 전혀 사용할 수 없게 된다.
이 문제를 보고 가장 먼저 떠오른 생각은 큐브 블라인드처럼 푸는것이였다. 간단하게 말하면, 모든 큐브 조각의 '위치'에 번호를 붙여준 뒤, 실제로 알맞는 '위치'에 들어가야할 조각들을 바꾸는 것이다. 이후 방향을 맞추는 움직임을 다시 해주면 된다.
큐브 조각의 위치를 맞추는 과정을 '오리엔테이션' 이라고 하고, 방향을 맞추는 방향을 '퍼뮤테이션' 이라고 한다.
나는 풀이의 편의성과 구현을 간결히 하기 위해, 다른 조각에 영향을 끼치지 않고 오로지 두 조각의 위치만을 바꾸는 공식을 적용하였다. 이제 위치를 정의해보자. 움직일 수 없는 고정된 조각을 8번으로 하고, 시계방향으로 7 6 5번 조각으로 지정한다.
마찬가지로 위층도 4번부터 시계방향으로 3 2 1번 조각으로 지정한다.
내가 사용한 공식은 4번 조각과 6번 조각의 위치를 바꾸는 공식인데, 이를 위해 나머지 쌍은 '셋업무브'를 해주어야한다.
예를 들어 바꾸고 싶은 조각이 3번과 6번에 있다고 하자. 우리는 4번과 6번 조각의 위치를 바꿀 수 있기 때문에, 이 경우 Y move를 통해 3번조각을 4번위치로 옮기고 공식을 쓴 뒤, YYY move를 통해 원래 자리로 돌려보내면 된다. 여기서 위치를 옮겨 4번과 6번 위치에 오게 해주는 무브가 셋업무브이다.
8번 조각은 움직이지 않기 때문에, 1번부터 7번 조각까지 가능한 조각 위치 조합에 대해 전처리를 해준다. 이후 실행하면, '오리엔테이션'이 완료된다.
퍼뮤테이션도 간단하다. 문제에서 주어지는 전개도의 큐브는 모두 맞출 수 있는 큐브이기 때문에 확신을 가지고 풀면 된다.
나는 1번 조각과 2번 조각의 방향을 동시에 바꾸는 공식을 사용하였다. 이 역시 셋업무브를 전처리 해주면 된다.
여기서 주의할 점은, 동시에 바꾸는 조각 쌍을 지정하는 것이다. 예를 들어 1번 조각의 방향을 알맞게 하고 싶다면, 이미 맞춰진 조각을 제외하고 1번 조각과 동시에 방향을 바꿔줄 조각이 필요하다. 따라서 공식을 적용할 때. 인접한 맞춰지지 않은 조각이 항상 필요하며, 이를 위해서는 조각쌍을 다음과 같이 지정할 수 있다.
(방향을 맞출 조각)-(공식에 참여해 방향이 바뀌는 조각)
4-3
3-2
2-1
1-5
5-6
6-7
8번 조각을 기준으로 맞췄기 때문에 8번 조각은 퍼뮤테이션이 필요없다. 또한, 맞출 수 있는 큐브라면 항상 마지막 6-7 퍼뮤테이션에서 두 조각이 동시에 맞춰지게 된다. 따라서 저 순서대로 조각을 맞추고 나면, 큐브는 완성된 상태가 된다.
나는 MITM에 관련된 문제를 하나도 풀어보지 않아서, 이 문제를 통해 처음 접하게 되었다. 결과적으로는 구현만으로 해결하긴 했지만, 이 문제의 어려운 버전은 최소 이동 횟수까지 구해야하기 때문에 이걸 해결하기 위해선 MITM이 반드시 필요하다.
var v = 'XXXYXYXXXYYYXZXXXYYYXYXZZZXXX' //4 6 위치바꾸기
var v2 = 'YYXZZZYXXXYXYYZZXXXY' //1 2 방향바꾸기
var rs = [//마주보는 면 순서쌍
[['W','Y'],['B','G'],['R','O']],
[['W','Y'],['B','R'],['G','O']],
[['W','Y'],['B','O'],['G','R']],
[['W','Y'],['G','R'],['B','O']],
[['W','Y'],['G','O'],['B','R']],
[['W','Y'],['R','O'],['B','G']],
[['W','B'],['Y','G'],['R','O']],
[['W','B'],['Y','R'],['G','O']],
[['W','B'],['Y','O'],['G','R']],
[['W','B'],['G','R'],['Y','O']],
[['W','B'],['G','O'],['Y','R']],
[['W','B'],['R','O'],['Y','G']],
[['W','G'],['Y','B'],['R','O']],
[['W','G'],['Y','R'],['B','O']],
[['W','G'],['Y','O'],['B','R']],
[['W','G'],['B','R'],['Y','O']],
[['W','G'],['B','O'],['Y','R']],
[['W','G'],['R','O'],['Y','B']],
[['W','R'],['Y','B'],['G','O']],
[['W','R'],['Y','G'],['B','O']],
[['W','R'],['Y','O'],['B','G']],
[['W','R'],['B','G'],['Y','O']],
[['W','R'],['B','O'],['Y','G']],
[['W','R'],['G','O'],['Y','B']],
[['W','O'],['Y','B'],['G','R']],
[['W','O'],['Y','G'],['B','R']],
[['W','O'],['Y','R'],['B','G']],
[['W','O'],['B','G'],['Y','R']],
[['W','O'],['B','R'],['Y','G']],
[['W','O'],['G','R'],['Y','B']],
[['Y','B'],['W','G'],['R','O']],
[['Y','B'],['W','R'],['G','O']],
[['Y','B'],['W','O'],['G','R']],
[['Y','B'],['G','R'],['W','O']],
[['Y','B'],['G','O'],['W','R']],
[['Y','B'],['R','O'],['W','G']],
[['Y','G'],['W','B'],['R','O']],
[['Y','G'],['W','R'],['B','O']],
[['Y','G'],['W','O'],['B','R']],
[['Y','G'],['B','R'],['W','O']],
[['Y','G'],['B','O'],['W','R']],
[['Y','G'],['R','O'],['W','B']],
[['Y','R'],['W','B'],['G','O']],
[['Y','R'],['W','G'],['B','O']],
[['Y','R'],['W','O'],['B','G']],
[['Y','R'],['B','G'],['W','O']],
[['Y','R'],['B','O'],['W','G']],
[['Y','R'],['G','O'],['W','B']],
[['Y','O'],['W','B'],['G','R']],
[['Y','O'],['W','G'],['B','R']],
[['Y','O'],['W','R'],['B','G']],
[['Y','O'],['B','G'],['W','R']],
[['Y','O'],['B','R'],['W','G']],
[['Y','O'],['G','R'],['W','B']],
[['B','G'],['W','Y'],['R','O']],
[['B','G'],['W','R'],['Y','O']],
[['B','G'],['W','O'],['Y','R']],
[['B','G'],['Y','R'],['W','O']],
[['B','G'],['Y','O'],['W','R']],
[['B','G'],['R','O'],['W','Y']],
[['B','R'],['W','Y'],['G','O']],
[['B','R'],['W','G'],['Y','O']],
[['B','R'],['W','O'],['Y','G']],
[['B','R'],['Y','G'],['W','O']],
[['B','R'],['Y','O'],['W','G']],
[['B','R'],['G','O'],['W','Y']],
[['B','O'],['W','Y'],['G','R']],
[['B','O'],['W','G'],['Y','R']],
[['B','O'],['W','R'],['Y','G']],
[['B','O'],['Y','G'],['W','R']],
[['B','O'],['Y','R'],['W','G']],
[['B','O'],['G','R'],['W','Y']],
[['G','R'],['W','Y'],['B','O']],
[['G','R'],['W','B'],['Y','O']],
[['G','R'],['W','O'],['Y','B']],
[['G','R'],['Y','B'],['W','O']],
[['G','R'],['Y','O'],['W','B']],
[['G','R'],['B','O'],['W','Y']],
[['G','O'],['W','Y'],['B','R']],
[['G','O'],['W','B'],['Y','R']],
[['G','O'],['W','R'],['Y','B']],
[['G','O'],['Y','B'],['W','R']],
[['G','O'],['Y','R'],['W','B']],
[['G','O'],['B','R'],['W','Y']],
[['R','O'],['W','Y'],['B','G']],
[['R','O'],['W','B'],['Y','G']],
[['R','O'],['W','G'],['Y','B']],
[['R','O'],['Y','B'],['W','G']],
[['R','O'],['Y','G'],['W','B']],
[['R','O'],['B','G'],['W','Y']]
]
function FI(c) {
const IItr = (tr,pa) => {
for (var i = 0; i < 3; ++i) {
for (var j = i + 1; j < 3; ++j) {
var [a,b] = [tr[i],tr[j]]
for (var [x,y] of pa) {
if ((a == x && b == y) || (a == y && b == x)) {
return true
}
}
}
}
return false
}
for (var pa of rs) {
var valid = true
for (var tr of c) {
var chars = tr.split('')
if (IItr(chars,pa)) {
valid = false
break
}
}
if (valid) return pa
}
return null
}
function N(s) {//셋업 무브 역순으로 설정해주는 함수. 예를 들어 YZZZ가 셋업무브라면 원래대로 돌려놓을때는 ZYYY가 된다.
var n = s.length
var transformed = Array(n).fill(null)
var used = Array(n).fill(false)
for (var i = 0; i < n; i++) {
var t = s[i]
if (used[i]) continue
var prev = i > 0 ? s[i - 1] : null
var next = i < n - 1 ? s[i + 1] : null
if ((prev != t) && (next != t)) {
transformed[i] = t + t + t
used[i] = true
}
}
for (var i = 0; i < n-2; i++) {
if (used[i] || used[i+1] || used[i+2]) continue
var a = s[i]
var b = s[i+1]
var c = s[i+2]
if (a == b && b == c) {
transformed[i] = a
used[i] = used[i+1] = used[i+2] = true
}
}
for (var i = 0; i < n; i++) {
if (!used[i]) {
transformed[i] = s[i]
}
}
return transformed.reverse().join('')
}
const M = x => x+v+N(x)
var setupMove = [[],//4 6
[0,0, M('XYYY'),M('YX'), M('ZZ'),M('YYYZ'),M('YYY'), M('XXXYYY')],
[0,M('XYYY'), 0, M('YXX'),M('X'), M('ZYYY'),M('YY'), M('XY')],
[0,M('YX'), M('YXX'),0, M('XX'),M('ZY'), M('Y'), M('XXYY')],
[0,M('ZZ'), M('X'), M('XX'), 0, M('Z'), v, M('XXX')],
[0,M('YYYZ'), M('ZYYY'),M('ZY'), M('Z'), 0, M('ZYY'), M('XXYYZ')],
[0,M('YYY'), M('YY'), M('Y'), v, M('ZYY'), 0, M('XXXYY')],
[0,M('XXXYYY'),M('XY'), M('XXYY'),M('XXX'),M('XXYYZ'),M('XXXYY'),0]]
class CubeO { //W,Y,B,G,R,O
constructor(s) {
this.grids = s.split('\n').map(e=>e.split(''))
var g = this.grids
var c = [
g[1][2]+g[2][1]+g[2][2],
g[1][3]+g[2][3]+g[2][4],
g[3][2]+g[3][1]+g[4][2],
g[3][3]+g[3][4]+g[4][3],
g[3][0]+g[3][7]+g[5][2],
g[3][6]+g[3][5]+g[5][3],
g[0][3]+g[2][5]+g[2][6],
g[0][2]+g[2][0]+g[2][7]
]
var kk = FI(c)
var k1 = new RegExp(kk[0][0],'g')
var k6 = new RegExp(kk[0][1],'g')
var k2 = new RegExp(kk[1][0],'g')
var k5 = new RegExp(kk[1][1],'g')
var k3 = new RegExp(kk[2][0],'g')
var k4 = new RegExp(kk[2][1],'g')
this.grid = s.replace(/\./g,'0').replace(k1,'1').replace(k2,'2').replace(k3,'3').replace(k4,'4').replace(k5,'5').replace(k6,'6').split('\n').map(e => e.split('').map(Number))
this.O = [0,1,2,3,4,5,6,7,8]
this.move = ''
}
show() {
return this.grid.map(e => e.join('')).join('\n') + '\n'
}
history() {
return this.move
}
moveX(n) {
for(var i = 0; i < n; i++) {
this.move += 'X'
var g = this.grid
var [u1,u2,temp] = [g[0][3],g[1][3],g[2][4]]
g[1][3] = g[2][6]
g[0][3] = g[3][6]
g[3][6] = g[4][3]
g[2][6] = g[5][3]
g[4][3] = g[2][3]
g[5][3] = g[3][3]
g[2][3] = u1
g[3][3] = u2
g[2][4] = g[2][5]
g[2][5] = g[3][5]
g[3][5] = g[3][4]
g[3][4] = temp
}
}
moveY(n) {
for(var i = 0; i < n; i++) {
this.move += 'Y'
var g = this.grid
g[2] = [g[2][6],g[2][7],g[2][0],g[2][1],g[2][2],g[2][3],g[2][4],g[2][5]]
var temp = g[0][2]
g[0][2] = g[0][3]
g[0][3] = g[1][3]
g[1][3] = g[1][2]
g[1][2] = temp
}
}
moveZ(n) {
for(var i = 0; i < n; i++) {
this.move += 'Z'
var g = this.grid
var [u1,u2,temp] = [g[1][2],g[1][3],g[2][2]]
g[1][2] = g[2][4]
g[1][3] = g[3][4]
g[2][4] = g[4][3]
g[3][4] = g[4][2]
g[4][3] = g[3][1]
g[4][2] = g[2][1]
g[3][1] = u1
g[2][1] = u2
g[2][2] = g[2][3]
g[2][3] = g[3][3]
g[3][3] = g[3][2]
g[3][2] = temp
}
}
moveing(s) {
for(var i = 0; i < s.length; i++) {
if(s[i] == 'X') this.moveX(1)
else if(s[i] == 'Y') this.moveY(1)
else if(s[i] == 'Z') this.moveZ(1)
}
}
findS(i,j) {
var z = `
0 0 4 3 0 0 0 0
0 0 1 2 0 0 0 0
4 1 1 2 2 3 3 4
8 5 5 6 6 7 7 8
0 0 5 6 0 0 0 0
0 0 8 7 0 0 0 0
`.trim().split('\n').map(e=>e.split(' ').map(Number))
var zz = []
for(var ii = 0; ii < 6; ii++) {
for(var jj = 0; jj < 8; jj++) {
if(i==ii && j==jj) continue
if(z[i][j] == z[ii][jj]) zz.push((this.grid)[ii][jj])
}
}
return [zz,z[i][j]]
}
P(n) {
if(n == 1) {
this.moveing('ZZZ'+v2+'Z')
}else if(n == 2) {
this.moveing(v2)
}else if(n == 3) {
this.moveing('YYY'+v2+'Y')
}else if(n == 4) {
this.moveing('YY'+v2+'YY')
}else if(n == 5) {
this.moveing('ZZ'+v2+'ZZ')
}else if(n == 6) {
this.moveing('XXYYY'+v2+'YXX')
}
}
}
var input = require('fs').readFileSync(0,'utf8').trim().split('\n\n')
for(var q = 0; q < input.length - 1; q++) {
var cube = new CubeO(input[q])
var g = cube.grid
var o = cube.O
var dColor = g[5][2]
var uColor = 7 - dColor
for(var i = 0; i < 6; i++) {
for(var j = 0; j < 8; j++) {
if(i == 5 && j == 2) continue
if(g[i][j] == dColor) {
var [z,d] = cube.findS(i,j)
if(z.includes(g[3][0])) {
o[d] = 5
}else if(z.includes(g[3][7])) {
o[d] = 7
}else {
o[d] = 6
}
}else if(g[i][j] == uColor) {
var [z,d] = cube.findS(i,j)
if(z.includes(7 - g[3][0]) && z.includes(7 - g[3][7])) {
o[d] = 2
}else if(z.includes(7 - g[3][0])) {
o[d] = 3
}else if(z.includes(7 - g[3][7])) {
o[d] = 1
}else {
o[d] = 4
}
}
}
}
var dab = ''
for(var i = 1; i < 8; i++) {
while(o[i] != i) {
var temp = o[i]
o[i] = o[temp]
o[temp] = temp
dab += setupMove[i][temp]
}
}
cube.moveing(dab)
var l = [0,[1,2],[1,3],[0,3],[0,2],[4,2],[4,3],[5,3]]
for(var i = 4; i >= 1; i--) {//12 13 03 02 42 43 53
while(g[l[i][0]][l[i][1]] != uColor) {
cube.P(i)
}
}
for(var i = 5; i <= 6; i++) {//12 13 03 02 42 43 53
while(g[l[i][0]][l[i][1]] != dColor) {
cube.P(i)
}
}
console.log(cube.history().replace(/XXXX/g,'').replace(/YYYY/g,'').replace(/ZZZZ/g,''))
}
'PS 풀이' 카테고리의 다른 글
| [백준 34019] [G] Grounded Number (0) | 2025.08.11 |
|---|---|
| [백준 18789] 814 - 2 (11008점) (0) | 2025.07.03 |
| [백준 22222] 지애 상수 (0) | 2025.02.19 |
| [백준 13480] Hard Cuts (0) | 2025.01.30 |
| [백준 1784] 팰린드롬 인코딩 (0) | 2025.01.28 |
