유튜브를 보다가 오랜만에 레이튼 교수 시리즈를 다시 접하게 되었습니다. 모바일 버전이 있다는 걸 알게 되어 설치하고 플레이해봤는데, 마지막 문제가 정말 인상 깊었어요.
블럭을 움직여 빨간 사각형을 밖으로 빼내는 문제였습니다. 이건 누가 봐도 코딩으로 해결을 하라는 거죠. 바로 visual studio를 켜줍니다.
알고리즘
각 판의 상태를 정점으로, 한 상태에서 다른 상태로 이동할 수 있을 때 간선으로 연결을 해 주면 그래프가 만들어 집니다. 그럼 다익스트라나 BFS를 통해서 이 문제를 해결할 수 있습니다.
정점
빈 칸도 블럭이라 생각을 하고 각 블럭의 좌측 상단에 번호를 매깁니다. 빈칸은 0, 초록색은 1, 파란색은 2, 보라색은 3, 빨간색은 4로 번호를 매겨줍니다.
왼쪽 위부터 오른쪽으로 쭉 가면서 숫자를 읽어줍니다. 숫자가 없는 곳은 넘어갑니다. 위 그림은 221431010221이 됩니다. 이 숫자를 5진수로 생각하고 10진수로 변환하면 숫자 하나로 판의 상태를 나타낼 수 있습니다. 최악의 경우 229488275니까 long long으로 충분히 표현 가능합니다.
그럼 다음 알고리즘을 생각할 수 있습니다.
- 처음 판의 상태를 큐에 넣어둡니다..
- 큐에 있는 숫자를 꺼내고 해당 숫자를 판으로 바꿉니다.
- 이동 가능한 모든 판의 상태를 구하고 해당 판을 큐에 넣어둡니다.
- 빨간 블럭이 출구로 도달하면 프로그램을 종료합니다.
시간복잡도
bfs로 하면 $O(M)$에 해결이 가능하겠지만 저는 다익스트라를 이용해 $O(M\log M)$ 해결을 했습니다. $M$은 간선의 개수입니다.
정점의 개수는 $5^{12}$인것 같지만 사실 각 블럭의 개수는 변하지 않습니다. 즉 12개의 칸에 4 1개, 3 1개, 2 4개, 1 4개, 0 2개를 배치하는 경우의 수를 구하면 415800개가 됩니다.
블럭은 항상 빈칸으로 움직일 수 있습니다. 빈 칸이 2개고 각 빈 칸 마다 상하좌우로 들어올 수 있으니 각 상태 당 최대 8개의 이동이 가능합니다. 이러면 1초 안에는 충분히 해결할 수 있습니다.
코드
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<queue>
#include<map>
using namespace std;
priority_queue<pair<int, long long int>> q;
map<long long int, int>mm;
map<long long int, int>back;
int mapp[8][8], n = 4, m = 5,path[10000], cnt = 0;
// 숫자를 판으로
void get(long long int v) {
int i, j, base = 48828125; // 5**11
// 초기화
for (i = 0;i <= n+1;i++) {
for (j = 0;j <= m+1;j++) {
mapp[i][j] = -1;
}
}
for (i = 1;i <= n;i++) {
for (j = 1;j <= m;j++) {
if (mapp[i][j] != -1) continue;
if (v / base == 0) mapp[i][j] = 0;
else if (v / base == 1) mapp[i][j] = 1;
else if (v / base == 2) {
mapp[i][j] = 2;
mapp[i][j + 1] = 2;
}
else if (v / base == 3) {
mapp[i][j] = 3;
mapp[i + 1][j] = 3;
}
else if (v / base == 4) {
mapp[i][j] = 4;
mapp[i + 1][j] = 4;
mapp[i][j + 1] = 4;
mapp[i + 1][j + 1] = 4;
}v %= base;
base /= 5;
}
}
}
// 판을 숫자로
long long int get_v() {
int i, j;
long long int v = 0, base = 48828125; // 5**11
for (i = 1;i <= n;i++) {
for (j = 1;j <= m;j++) {
if (mapp[i][j] == 0) { base /= 5;continue; }
else if (mapp[i][j] == 1) {
v += base;
base /= 5;
}
else if (mapp[i][j] == 2) {
v += base*2;
j++;
base /= 5;
}
else if (mapp[i][j] == 3) {
if (mapp[i - 1][j] == 3) continue;
v += base * 3;
base /= 5;
}
else if (mapp[i][j] == 4) {
if (mapp[i + 1][j + 1] != 4) continue;
v += base * 4;
base /= 5;
}
}
}
return v;
}
// 움직일 수 있는 모든 경우 계산
void move(long long int vv,int cc) {
int i, j, tmap[8][8];
long long int v;
for (i = 0;i <= n+1;i++) {
for (j = 0;j <= m+1;j++) {
tmap[i][j] = mapp[i][j];
}
}
for (i = 1;i <= n;i++) {
for (j = 1;j <= m;j++) {
if (tmap[i][j] == -1) continue;
if (tmap[i][j] == 1) {
if (mapp[i][j + 1] == 0) {
mapp[i][j] = 0;
mapp[i][j + 1] = 1;
v = get_v();
if (mm.find(v) == mm.end()) {
mm[v] = cc + 1;
q.push({ -(cc + 1), v });
back[v] = vv;
}
mapp[i][j] = 1;
mapp[i][j + 1] = 0;
}
if (mapp[i][j - 1] == 0) {
mapp[i][j] = 0;
mapp[i][j - 1] = 1;
v = get_v();
if (mm.find(v) == mm.end()) {
mm[v] = cc + 1;
q.push({ -(cc + 1), v });
back[v] = vv;
}
mapp[i][j] = 1;
mapp[i][j - 1] = 0;
}
if (mapp[i + 1][j] == 0) {
mapp[i][j] = 0;
mapp[i + 1][j] = 1;
v = get_v();
if (mm.find(v) == mm.end()) {
mm[v] = cc + 1;
q.push({ -(cc + 1), v });
back[v] = vv;
}
mapp[i][j] = 1;
mapp[i + 1][j] = 0;
}
if (mapp[i - 1][j] == 0) {
mapp[i][j] = 0;
mapp[i - 1][j] = 1;
v = get_v();
if (mm.find(v) == mm.end()) {
mm[v] = cc + 1;
q.push({ -(cc + 1), v });
back[v] = vv;
}
mapp[i][j] = 1;
mapp[i - 1][j] = 0;
}
tmap[i][j] = -1;
}
if (tmap[i][j] == 2) {
if (mapp[i][j + 2] == 0) {
mapp[i][j] = 0;
mapp[i][j + 2] = 2;
v = get_v();
if (mm.find(v) == mm.end()) {
mm[v] = cc + 1;
q.push({ -(cc + 1), v });
back[v] = vv;
}
mapp[i][j] = 2;
mapp[i][j + 2] = 0;
}
if (mapp[i][j - 1] == 0) {
mapp[i][j+1] = 0;
mapp[i][j - 1] = 2;
v = get_v();
if (mm.find(v) == mm.end()) {
mm[v] = cc + 1;
q.push({ -(cc + 1), v });
back[v] = vv;
}
mapp[i][j+1] = 2;
mapp[i][j - 1] = 0;
}
if (mapp[i + 1][j] == 0 && mapp[i + 1][j + 1] == 0) {
mapp[i][j] = 0;
mapp[i + 1][j] = 2;
mapp[i][j + 1] = 0;
mapp[i + 1][j + 1] = 2;
v = get_v();
if (mm.find(v) == mm.end()) {
mm[v] = cc + 1;
q.push({ -(cc + 1), v });
back[v] = vv;
}
mapp[i][j] = 2;
mapp[i + 1][j] = 0;
mapp[i][j + 1] = 2;
mapp[i + 1][j + 1] = 0;
}
if (mapp[i - 1][j] == 0 && mapp[i - 1][j + 1] == 0) {
mapp[i][j] = 0;
mapp[i - 1][j] = 2;
mapp[i][j + 1] = 0;
mapp[i - 1][j + 1] = 2;
v = get_v();
if (mm.find(v) == mm.end()) {
mm[v] = cc + 1;
q.push({ -(cc + 1), v });
back[v] = vv;
}
mapp[i][j] = 2;
mapp[i - 1][j] = 0;
mapp[i][j + 1] = 2;
mapp[i - 1][j + 1] = 0;
}
tmap[i][j] = -1;
tmap[i][j+1] = -1;
}
if (tmap[i][j] == 3) {
if (mapp[i][j + 1] == 0 && mapp[i+1][j + 1] == 0) {
mapp[i][j] = 0;
mapp[i][j + 1] = 3;
mapp[i+1][j] = 0;
mapp[i+1][j + 1] = 3;
v = get_v();
if (mm.find(v) == mm.end()) {
mm[v] = cc + 1;
q.push({ -(cc + 1), v });
back[v] = vv;
}
mapp[i][j] = 3;
mapp[i][j + 1] = 0;
mapp[i + 1][j] = 3;
mapp[i + 1][j + 1] = 0;
}
if (mapp[i][j - 1] == 0 && mapp[i + 1][j - 1] == 0) {
mapp[i][j] = 0;
mapp[i][j - 1] = 3;
mapp[i + 1][j] = 0;
mapp[i + 1][j - 1] = 3;
v = get_v();
if (mm.find(v) == mm.end()) {
mm[v] = cc + 1;
q.push({ -(cc + 1), v });
back[v] = vv;
}
mapp[i][j] = 3;
mapp[i][j - 1] = 0;
mapp[i + 1][j] = 3;
mapp[i + 1][j - 1] = 0;
}
if (mapp[i + 2][j] == 0) {
mapp[i][j] = 0;
mapp[i + 2][j] = 3;
v = get_v();
if (mm.find(v) == mm.end()) {
mm[v] = cc + 1;
q.push({ -(cc + 1), v });
back[v] = vv;
}
mapp[i][j] = 3;
mapp[i + 2][j] = 0;
}
if (mapp[i - 1][j] == 0) {
mapp[i+1][j] = 0;
mapp[i - 1][j] = 3;
v = get_v();
if (mm.find(v) == mm.end()) {
mm[v] = cc + 1;
q.push({ -(cc + 1), v });
back[v] = vv;
}
mapp[i+1][j] = 3;
mapp[i - 1][j] = 0;
}
tmap[i][j] = -1;
tmap[i+1][j] = -1;
}
if (tmap[i][j] == 4) {
if (mapp[i][j + 2] == 0 && mapp[i + 1][j + 2] == 0) {
mapp[i][j] = 0;
mapp[i][j + 2] = 4;
mapp[i + 1][j] = 0;
mapp[i + 1][j + 2] = 4;
v = get_v();
if (mm.find(v) == mm.end()) {
mm[v] = cc + 1;
q.push({ -(cc + 1), v });
back[v] = vv;
}
mapp[i][j] = 4;
mapp[i][j + 2] = 0;
mapp[i + 1][j] = 4;
mapp[i + 1][j + 2] = 0;
}
if (mapp[i][j - 1] == 0 && mapp[i + 1][j - 1] == 0) {
mapp[i][j+1] = 0;
mapp[i][j - 1] = 4;
mapp[i + 1][j+1] = 0;
mapp[i + 1][j - 1] = 4;
v = get_v();
if (mm.find(v) == mm.end()) {
mm[v] = cc + 1;
q.push({ -(cc + 1), v });
back[v] = vv;
}
mapp[i][j+1] = 4;
mapp[i][j - 1] = 0;
mapp[i + 1][j+1] = 4;
mapp[i + 1][j - 1] = 0;
}
if (mapp[i + 2][j] == 0 && mapp[i + 2][j+1] == 0) {
mapp[i][j] = 0;
mapp[i + 2][j] = 4;
mapp[i][j + 1] = 0;
mapp[i + 2][j + 1] = 4;
v = get_v();
if (mm.find(v) == mm.end()) {
mm[v] = cc + 1;
q.push({ -(cc + 1), v });
back[v] = vv;
}
mapp[i][j] = 4;
mapp[i + 2][j] = 0;
mapp[i][j + 1] = 4;
mapp[i + 2][j + 1] = 0;
}
if (mapp[i - 1][j] == 0 && mapp[i - 1][j+1] == 0) {
mapp[i + 1][j] = 0;
mapp[i - 1][j] = 4;
mapp[i + 1][j+1] = 0;
mapp[i - 1][j+1] = 4;
v = get_v();
if (mm.find(v) == mm.end()) {
mm[v] = cc + 1;
q.push({ -(cc + 1), v });
back[v] = vv;
}
mapp[i + 1][j] = 4;
mapp[i - 1][j] = 0;
mapp[i + 1][j + 1] = 4;
mapp[i - 1][j + 1] = 0;
}
tmap[i][j] = -1;
tmap[i + 1][j] = -1;
tmap[i][j + 1] = -1;
tmap[i + 1][j + 1] = -1;
}
}
}
}
int main() {
int i, j, k;
// 초기값
q.push({ 0,120953811 });
// 해당 판의 상태가 어디서 왔는지 저장
back[120953811] = -1;
while (q.size()) {
int c = -q.top().first;
long long int v = q.top().second;
q.pop();
if (mm[v] != c) continue;
get(v);
// 종료 시점
if (mapp[2][5] == 4 && mapp[3][5] == 4) {
printf("END!\n");
// 경로 추출
while (v != -1) {
cnt++;
path[cnt] = v;
v = back[v];
}
// 판의 상태 출력
for (i = cnt;i >= 1;i--) {
get(path[i]);
for (j = 1;j <= n;j++) {
for (k = 1;k <= m;k++) {
printf("%d", mapp[j][k]);
}
printf("\n");
}
printf("\n");
scanf("%*c");
}
return 0;
}
move(v, c);
}
return 0;
}'프로젝트' 카테고리의 다른 글
| 웹 개발 - 프로젝트 2 - 6. streak lover 로그인 (2) | 2024.09.14 |
|---|---|
| 웹 개발 - 프로젝트 2 - 5. streak lover 백엔드 api (0) | 2024.08.24 |
| 웹 개발 - 프로젝트 2 - 4. streak lover 백엔드 db (0) | 2024.08.18 |
| 웹 개발 - 프로젝트 2 - 3. streak lover 프론트 (0) | 2024.08.07 |
| 웹 개발 - 프로젝트 2 - 2. streak lover 프론트 (0) | 2024.08.05 |
