퍼즐
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 32 MB (하단 참고) | 6045 | 2198 | 1203 | 34.322% |
문제
3*3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.
| 1 | 2 | 3 |
|---|---|---|
| 4 | 5 | 6 |
| 7 | 8 |
어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자.
| 1 | 3 | |
|---|---|---|
| 4 | 2 | 5 |
| 7 | 8 | 6 |
| 1 | 2 | 3 |
|---|---|---|
| 4 | 5 | |
| 7 | 8 | 6 |
| 1 | 2 | 3 |
|---|---|---|
| 4 | 5 | |
| 7 | 8 | 6 |
| 1 | 2 | 3 |
|---|---|---|
| 4 | 5 | 6 |
| 7 | 8 |
가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.
입력
세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.
출력
첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.
예제 입력 1
1
2
3
1 0 3
4 2 5
7 8 6
예제 출력 1
1
3
풀이
dfs로 풀라고 했는데 실패했다. 지나온 길을 체크하면서 체크안한길로 가는데 12345678이 될때를 구하려고 했다..
생각해보니 내 방법으로 풀면 총 갈 수 있는 블럭의 수가 8개 밖에 안됐다..
그래서 그러면 바로 전 좌표만 안가는 방법으로 해야겠다 ! 라고 생각해서 다시 코드를 짰는데
이렇게 푸니까 똑같은 좌표(2,2 -> 2,3->3,3->3,2->2,2 ,,,,)를 무한히 돌아 dfs을 빠져나올 수 없었다,,,,,,,,,,,,,,
멘붕…
어떻게 풀어야 할지 모르겠다 ㅠㅠ비트마스크를 써서 푼다는데 …………ㅠㅠㅠㅠㅠㅠㅠ
나중에 꼭 풀어줄게…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int mincnt=1000000;
int dy[]= {0,1,0,-1};
int dx[]= {1,0,-1,0};
vector<vector<int>> v;
vector<vector<int>> check;
bool puzzle(){
for(int num=1,i=0;i<3;i++){
for(int j=0;j<3;j++){
if(i==2 && j==2)
return true;
if(v[i][j]!=num)
return false;
num++;
}
}
return true;
}
void dfs(int y,int x,int pre_y,int pre_x,int cnt){
if(y==2 && x==2){
if(puzzle())
mincnt=min(cnt,mincnt);
return;
}
for(int i=0;i<4;i++){
if(y+dy[i] < 0 || y+dy[i] >= 3 || x+dx[i] <0 ||x+dx[i] >=3) continue;
// if(check[y+dy[i]][x+dx[i]]==0){
if(y+dy[i]== pre_y && x+dx[i]==pre_x) continue;
int ne; //0값 움직인다.
ne=v[y][x];
v[y][x]=v[y+dy[i]][x+dx[i]];
v[y+dy[i]][x+dx[i]]=ne;
check[y][x]=1;
// check[y+dy[i]][x+dx[i]]=1;
dfs(y+dy[i],x+dx[i],y,x,cnt+1);
ne=v[y][x];
v[y][x]=v[y+dy[i]][x+dx[i]];
v[y+dy[i]][x+dx[i]]=ne;
check[y][x]=0;
// check[y+dy[i]][x+dx[i]]=0;
// } //check
}
}
/* 반례
2 5 7
8 0 3
4 1 6
18
6 4 7
8 5 0
3 2 1
31
*/
int main(){
int i,j,Y=0,X=0;
v.resize(3); check.resize(3);
for(i=0;i<3;i++){
v[i].resize(3);
check[i].resize(3,0);
for(j=0;j<3;j++){
int temp;
cin >>temp;
if(temp==0){
Y=i;
X=j;
}
v[i][j]=temp;
}
} //퍼즐 입력
// check[Y][X]=1;
dfs(Y,X,-1,-1,0);// y,x, cnt;
// if(mincnt != 1000000)
cout << mincnt << '\n';
// else
// cout << -1 << '\n';
}