Categories: 알고리즘
백준 5373번 - 큐빙
큐빙 (백준 5373번)
개념 : 구현
난이도 : 
링크 : 큐빙 : https://www.acmicpc.net/problem/5373
꽤나 악명 높은 삼성 SW 역량테스트 A형 기출문제이다. 정말 놀랍게도 단 하나의 추가적인 개념이 필요하지 않고, 색을 회전에 따라 바꾸면 된다. 나는 큐브를 오래전부터 했었기 때문에, orientation의 개념을 이용해서 조각별로 관리하여 AC를 받았지만, 이 풀이는 아마 이해하기 힘들 것이다.
이번에 C++로 다시 풀이하면서 좀 더 좋은 아이디어가 생각났다. 단순히 각 면의 색을 위치나 행렬로 표현하는 것보다, 문자열로 만들어서 이해하기 편하기 만들었다.
문자열 규칙은 다음과 같은 예시로 정했다.
FUL : F면의 U면과 붙어있고, L면과 붙어있는 조각
뒤 두 문자는 순서가 상관 없는데, U면과 D면에 우선순위를 주었다.
그리고 C++ STL의 std::tuple과 std::tie를 적극적으로 이용하면 보다 직관적으로 회전을 표현할 수 있다.
이제, 더 이상의 설명은 생략한다.
#include <bits/stdc++.h>
using namespace std;
using pc12 = tuple<char, char, char, char, char, char,
char, char, char, char, char, char>;
using pc9 = tuple<char, char, char, char, char, char,
char, char, char>;
unordered_map<string, char> INIT = {
{"FUL" , 'r'}, {"FU", 'r'}, {"FUR", 'r'},
{"FL", 'r'}, {"F", 'r'}, {"FR", 'r'},
{"FDL", 'r'}, {"FD", 'r'}, {"FDR", 'r'},
{"UBL", 'w'}, {"UB", 'w'}, {"UBR", 'w'},
{"UL", 'w'}, {"U", 'w'}, {"UR", 'w'},
{"UFL", 'w'}, {"UF", 'w'}, {"UFR", 'w'},
{"DFL", 'y'}, {"DF", 'y'}, {"DFR", 'y'},
{"DL", 'y'}, {"D", 'y'}, {"DR", 'y'},
{"DBL", 'y'}, {"DB", 'y'}, {"DBR", 'y'},
{"BDL", 'o'}, {"BD", 'o'}, {"BDR", 'o'},
{"BL", 'o'}, {"B", 'o'}, {"BR", 'o'},
{"BUL" , 'o'}, {"BU", 'o'}, {"BUR", 'o'},
{"LUB", 'g'}, {"LU", 'g'}, {"LUF", 'g'},
{"LB", 'g'}, {"L", 'g'}, {"LF", 'g'},
{"LDB", 'g'}, {"LD", 'g'}, {"LDF", 'g'},
{"RUF", 'b'}, {"RU", 'b'}, {"RUB", 'b'},
{"RF", 'b'}, {"R", 'b'}, {"RB", 'b'},
{"RDF", 'b'}, {"RD", 'b'}, {"RDB", 'b'}
};
unordered_map<string, char> CUBE;
void R() {
tie(
CUBE["FUR"], CUBE["FR"], CUBE["FDR"],
CUBE["UBR"], CUBE["UR"], CUBE["UFR"],
CUBE["BDR"], CUBE["BR"], CUBE["BUR"],
CUBE["DFR"], CUBE["DR"], CUBE["DBR"]
) =
pc12(
CUBE["DFR"], CUBE["DR"], CUBE["DBR"],
CUBE["FUR"], CUBE["FR"], CUBE["FDR"],
CUBE["UBR"], CUBE["UR"], CUBE["UFR"],
CUBE["BDR"], CUBE["BR"], CUBE["BUR"]
);
tie(
CUBE["RUF"], CUBE["RU"], CUBE["RUB"],
CUBE["RF"], CUBE["R"], CUBE["RB"],
CUBE["RDF"], CUBE["RD"], CUBE["RDB"]
) =
pc9(
CUBE["RDF"], CUBE["RF"], CUBE["RUF"],
CUBE["RD"], CUBE["R"], CUBE["RU"],
CUBE["RDB"], CUBE["RB"], CUBE["RUB"]
);
}
void R_() {
tie(
CUBE["DFR"], CUBE["DR"], CUBE["DBR"],
CUBE["FUR"], CUBE["FR"], CUBE["FDR"],
CUBE["UBR"], CUBE["UR"], CUBE["UFR"],
CUBE["BDR"], CUBE["BR"], CUBE["BUR"]
) =
pc12(
CUBE["FUR"], CUBE["FR"], CUBE["FDR"],
CUBE["UBR"], CUBE["UR"], CUBE["UFR"],
CUBE["BDR"], CUBE["BR"], CUBE["BUR"],
CUBE["DFR"], CUBE["DR"], CUBE["DBR"]
);
tie(
CUBE["RDF"], CUBE["RF"], CUBE["RUF"],
CUBE["RD"], CUBE["R"], CUBE["RU"],
CUBE["RDB"], CUBE["RB"], CUBE["RUB"]
) =
pc9(
CUBE["RUF"], CUBE["RU"], CUBE["RUB"],
CUBE["RF"], CUBE["R"], CUBE["RB"],
CUBE["RDF"], CUBE["RD"], CUBE["RDB"]
);
}
void L() {
tie(
CUBE["FUL"], CUBE["FL"], CUBE["FDL"],
CUBE["UBL"], CUBE["UL"], CUBE["UFL"],
CUBE["BDL"], CUBE["BL"], CUBE["BUL"],
CUBE["DFL"], CUBE["DL"], CUBE["DBL"]
) =
pc12(
CUBE["UBL"], CUBE["UL"], CUBE["UFL"],
CUBE["BDL"], CUBE["BL"], CUBE["BUL"],
CUBE["DFL"], CUBE["DL"], CUBE["DBL"],
CUBE["FUL"], CUBE["FL"], CUBE["FDL"]
);
tie(
CUBE["LUB"], CUBE["LU"], CUBE["LUF"],
CUBE["LB"], CUBE["L"], CUBE["LF"],
CUBE["LDB"], CUBE["LD"], CUBE["LDF"]
) =
pc9(
CUBE["LDB"], CUBE["LB"], CUBE["LUB"],
CUBE["LD"], CUBE["L"], CUBE["LU"],
CUBE["LDF"], CUBE["LF"], CUBE["LUF"]
);
}
void L_() {
tie(
CUBE["UBL"], CUBE["UL"], CUBE["UFL"],
CUBE["BDL"], CUBE["BL"], CUBE["BUL"],
CUBE["DFL"], CUBE["DL"], CUBE["DBL"],
CUBE["FUL"], CUBE["FL"], CUBE["FDL"]
) =
pc12(
CUBE["FUL"], CUBE["FL"], CUBE["FDL"],
CUBE["UBL"], CUBE["UL"], CUBE["UFL"],
CUBE["BDL"], CUBE["BL"], CUBE["BUL"],
CUBE["DFL"], CUBE["DL"], CUBE["DBL"]
);
tie(
CUBE["LDB"], CUBE["LB"], CUBE["LUB"],
CUBE["LD"], CUBE["L"], CUBE["LU"],
CUBE["LDF"], CUBE["LF"], CUBE["LUF"]
) =
pc9(
CUBE["LUB"], CUBE["LU"], CUBE["LUF"],
CUBE["LB"], CUBE["L"], CUBE["LF"],
CUBE["LDB"], CUBE["LD"], CUBE["LDF"]
);
}
void U() {
tie(
CUBE["FUL"], CUBE["FU"], CUBE["FUR"],
CUBE["RUF"], CUBE["RU"], CUBE["RUB"],
CUBE["BUR"], CUBE["BU"], CUBE["BUL"],
CUBE["LUB"], CUBE["LU"], CUBE["LUF"]
) =
pc12(
CUBE["RUF"], CUBE["RU"], CUBE["RUB"],
CUBE["BUR"], CUBE["BU"], CUBE["BUL"],
CUBE["LUB"], CUBE["LU"], CUBE["LUF"],
CUBE["FUL"], CUBE["FU"], CUBE["FUR"]
);
tie(
CUBE["UBL"], CUBE["UB"], CUBE["UBR"],
CUBE["UL" ], CUBE["U" ], CUBE["UR" ],
CUBE["UFL"], CUBE["UF"], CUBE["UFR"]
) =
pc9(
CUBE["UFL"], CUBE["UL"], CUBE["UBL"],
CUBE["UF" ], CUBE["U" ], CUBE["UB" ],
CUBE["UFR"], CUBE["UR"], CUBE["UBR"]
);
}
void U_() {
tie(
CUBE["RUF"], CUBE["RU"], CUBE["RUB"],
CUBE["BUR"], CUBE["BU"], CUBE["BUL"],
CUBE["LUB"], CUBE["LU"], CUBE["LUF"],
CUBE["FUL"], CUBE["FU"], CUBE["FUR"]
) =
pc12(
CUBE["FUL"], CUBE["FU"], CUBE["FUR"],
CUBE["RUF"], CUBE["RU"], CUBE["RUB"],
CUBE["BUR"], CUBE["BU"], CUBE["BUL"],
CUBE["LUB"], CUBE["LU"], CUBE["LUF"]
);
tie(
CUBE["UFL"], CUBE["UL"], CUBE["UBL"],
CUBE["UF" ], CUBE["U" ], CUBE["UB" ],
CUBE["UFR"], CUBE["UR"], CUBE["UBR"]
) =
pc9(
CUBE["UBL"], CUBE["UB"], CUBE["UBR"],
CUBE["UL" ], CUBE["U" ], CUBE["UR" ],
CUBE["UFL"], CUBE["UF"], CUBE["UFR"]
);
}
void D() {
tie(
CUBE["FDL"], CUBE["FD"], CUBE["FDR"],
CUBE["RDF"], CUBE["RD"], CUBE["RDB"],
CUBE["BDR"], CUBE["BD"], CUBE["BDL"],
CUBE["LDB"], CUBE["LD"], CUBE["LDF"]
) =
pc12(
CUBE["LDB"], CUBE["LD"], CUBE["LDF"],
CUBE["FDL"], CUBE["FD"], CUBE["FDR"],
CUBE["RDF"], CUBE["RD"], CUBE["RDB"],
CUBE["BDR"], CUBE["BD"], CUBE["BDL"]
);
tie(
CUBE["DFL"], CUBE["DF"], CUBE["DFR"],
CUBE["DL" ], CUBE["D" ], CUBE["DR" ],
CUBE["DBL"], CUBE["DB"], CUBE["DBR"]
) =
pc9(
CUBE["DBL"], CUBE["DL"], CUBE["DFL"],
CUBE["DB" ], CUBE["D" ], CUBE["DF" ],
CUBE["DBR"], CUBE["DR"], CUBE["DFR"]
);
}
void D_() {
tie(
CUBE["LDB"], CUBE["LD"], CUBE["LDF"],
CUBE["FDL"], CUBE["FD"], CUBE["FDR"],
CUBE["RDF"], CUBE["RD"], CUBE["RDB"],
CUBE["BDR"], CUBE["BD"], CUBE["BDL"]
) =
pc12(
CUBE["FDL"], CUBE["FD"], CUBE["FDR"],
CUBE["RDF"], CUBE["RD"], CUBE["RDB"],
CUBE["BDR"], CUBE["BD"], CUBE["BDL"],
CUBE["LDB"], CUBE["LD"], CUBE["LDF"]
);
tie(
CUBE["DBL"], CUBE["DL"], CUBE["DFL"],
CUBE["DB" ], CUBE["D" ], CUBE["DF" ],
CUBE["DBR"], CUBE["DR"], CUBE["DFR"]
) =
pc9(
CUBE["DFL"], CUBE["DF"], CUBE["DFR"],
CUBE["DL" ], CUBE["D" ], CUBE["DR" ],
CUBE["DBL"], CUBE["DB"], CUBE["DBR"]
);
}
void F() {
tie(
CUBE["UFL"], CUBE["UF"], CUBE["UFR"],
CUBE["LDF"], CUBE["LF"], CUBE["LUF"],
CUBE["DFR"], CUBE["DF"], CUBE["DFL"],
CUBE["RUF"], CUBE["RF"], CUBE["RDF"]
) =
pc12(
CUBE["LDF"], CUBE["LF"], CUBE["LUF"],
CUBE["DFR"], CUBE["DF"], CUBE["DFL"],
CUBE["RUF"], CUBE["RF"], CUBE["RDF"],
CUBE["UFL"], CUBE["UF"], CUBE["UFR"]
);
tie(
CUBE["FUL"], CUBE["FU"], CUBE["FUR"],
CUBE["FL" ], CUBE["F" ], CUBE["FR" ],
CUBE["FDL"], CUBE["FD"], CUBE["FDR"]
) =
pc9(
CUBE["FDL"], CUBE["FL"], CUBE["FUL"],
CUBE["FD" ], CUBE["F" ], CUBE["FU" ],
CUBE["FDR"], CUBE["FR"], CUBE["FUR"]
);
}
void F_() {
tie(
CUBE["LDF"], CUBE["LF"], CUBE["LUF"],
CUBE["DFR"], CUBE["DF"], CUBE["DFL"],
CUBE["RUF"], CUBE["RF"], CUBE["RDF"],
CUBE["UFL"], CUBE["UF"], CUBE["UFR"]
) =
pc12(
CUBE["UFL"], CUBE["UF"], CUBE["UFR"],
CUBE["LDF"], CUBE["LF"], CUBE["LUF"],
CUBE["DFR"], CUBE["DF"], CUBE["DFL"],
CUBE["RUF"], CUBE["RF"], CUBE["RDF"]
);
tie(
CUBE["FDL"], CUBE["FL"], CUBE["FUL"],
CUBE["FD" ], CUBE["F" ], CUBE["FU" ],
CUBE["FDR"], CUBE["FR"], CUBE["FUR"]
) =
pc9(
CUBE["FUL"], CUBE["FU"], CUBE["FUR"],
CUBE["FL" ], CUBE["F" ], CUBE["FR" ],
CUBE["FDL"], CUBE["FD"], CUBE["FDR"]
);
}
void B() {
tie(
CUBE["LDB"], CUBE["LB"], CUBE["LUB"],
CUBE["DBR"], CUBE["DB"], CUBE["DBL"],
CUBE["RUB"], CUBE["RB"], CUBE["RDB"],
CUBE["UBL"], CUBE["UB"], CUBE["UBR"]
) =
pc12(
CUBE["UBL"], CUBE["UB"], CUBE["UBR"],
CUBE["LDB"], CUBE["LB"], CUBE["LUB"],
CUBE["DBR"], CUBE["DB"], CUBE["DBL"],
CUBE["RUB"], CUBE["RB"], CUBE["RDB"]
);
tie(
CUBE["BDR"], CUBE["BR"], CUBE["BUR"],
CUBE["BD" ], CUBE["B" ], CUBE["BU" ],
CUBE["BDL"], CUBE["BL"], CUBE["BUL"]
) =
pc9(
CUBE["BDL"], CUBE["BD"], CUBE["BDR"],
CUBE["BL" ], CUBE["B" ], CUBE["BR" ],
CUBE["BUL"], CUBE["BU"], CUBE["BUR"]
);
}
void B_() {
tie(
CUBE["UBL"], CUBE["UB"], CUBE["UBR"],
CUBE["LDB"], CUBE["LB"], CUBE["LUB"],
CUBE["DBR"], CUBE["DB"], CUBE["DBL"],
CUBE["RUB"], CUBE["RB"], CUBE["RDB"]
) =
pc12(
CUBE["LDB"], CUBE["LB"], CUBE["LUB"],
CUBE["DBR"], CUBE["DB"], CUBE["DBL"],
CUBE["RUB"], CUBE["RB"], CUBE["RDB"],
CUBE["UBL"], CUBE["UB"], CUBE["UBR"]
);
tie(
CUBE["BUL"], CUBE["BU"], CUBE["BUR"],
CUBE["BL" ], CUBE["B" ], CUBE["BR" ],
CUBE["BDL"], CUBE["BD"], CUBE["BDR"]
) =
pc9(
CUBE["BDL"], CUBE["BL"], CUBE["BUL"],
CUBE["BD" ], CUBE["B" ], CUBE["BU" ],
CUBE["BDR"], CUBE["BR"], CUBE["BUR"]
);
}
unordered_map<string, void (*)()> ROT = {
{"F+", F}, {"F-", F_},
{"B+", B}, {"B-", B_},
{"U+", U}, {"U-", U_},
{"D+", D}, {"D-", D_},
{"R+", R}, {"R-", R_},
{"L+", L}, {"L-", L_}
};
int main() {
int T; cin >> T;
while (T--) {
CUBE = INIT;
int m; cin >> m;
while (m--) {
string s;
cin >> s;
ROT[s]();
}
cout << CUBE["UBL"] << CUBE["UB"] << CUBE["UBR"] << '\n';
cout << CUBE["UL" ] << CUBE["U" ] << CUBE["UR" ] << '\n';
cout << CUBE["UFL"] << CUBE["UF"] << CUBE["UFR"] << '\n';
}
}
당연히 행렬이나, 배열로 표현하는게 더 빠르긴 한데, 시험을 본다고 했을 때, 위와 같이 표현하는 것이 더 디버깅하기 쉽다고 판단했다. 대략 90ms 정도에 통과한다.
Leave a comment