문제 URL : www.acmicpc.net/problem/1525
1525번: 퍼즐
세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.
www.acmicpc.net
문제 접근법
3*3 배열
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 0 |
인 배열형태로 만들면 끝나는 문제입니다. 그러나 어떻게 만들지 고민하셔야합니다.
첫번째 : 처음 숫자는 무작위로 주어지고 0인 숫자에서 좌우상하 자리를 바꾸어가면서 BFS를 이용하여 구하셔야합니다.
두번째 : 3*3 배열의 visit을 어떻게 처리할까? 이게 핵심이었습니다. 여러가지를 생각했지만 string의 해쉬코드를 응용하는 것이었습니다.
일반적인 string의 해시코드는
이러한 공식을 성립합니다. 공식에 나와있는 p는 소수이고 m은 적당히 큰수, s[i]는 ascii코드
즉 3*3 을 일차원인 배열로 만들때
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 |
이런형태가 끝이 되겠죠 이것을 문자열로 보면
"123456780" 이고 이것과 동일한 해쉬코드를(코드가 몇인지는 몰라도됨) 가질수있는 문자는 123456780뿐입니다.
그이유는 9개를 입력받고 0~8까지 중복없이 정확히 9개가 입력된다는것이 보장이 됩니다.
이러한 해쉬코드를 찾아서 visit을 처리한다면 3*3배열을 통해서 visit을해결할 수 있습니다.
세번째: 문자열의 해쉬코드를 이용할때 소수인 p는 대부분 31을 이용합니다.
처음 문제를 풀었을땐 31을 이용했지만
이문제는 입력조건이 제한적이라 소수가아닌 10을 이용해도 해쉬코드는 중복될 수 없습니다.
소스코드:
|
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
|
//By 콩순이냉장고
#include <iostream>
#include <unordered_set>
#include <cmath>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };
ll map[3][3];
struct puzzle{
ll board[3][3];
int cnt;
int y;//0위치 좌표
int x;
puzzle(ll board[3][3],int cnt){
this->cnt = cnt;
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++){
this->board[i][j] = board[i][j];
if (board[i][j] == 0){
y = i;
x = j;
}
}
}
}
};
ll hashcode(ll board[3][3]){
ll idx=0;
ll h = 0;
ll hcode = 10;//원래 문자열은 31인 소수를 이용 하지만 이 문제에선 10이어도 무방
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++){
h += board[i][j]*pow(hcode,idx++);
}
}
return h;
}
int bfs(){
ll finish[3][3] = {
{1,2,3},
{4,5,6},
{7,8,0}
};
ll finishcode = hashcode(finish);
queue<puzzle> q;
unordered_set<ll> visit;
q.push({map,0});
visit.insert(hashcode(map));
while (!q.empty()){
puzzle cur = q.front();
q.pop();
if (finishcode == hashcode(cur.board))
return cur.cnt;
for (int i = 0; i < 4; i++)
{
int ny = cur.y + dy[i];//0의 위치에서
int nx = cur.x + dx[i];
if (0 <= ny&&ny < 3 && 0 <= nx&&nx < 3){//동서남북 swap 돌릴수있는지 확인
ll nboard[3][3];
memcpy(nboard, cur.board, sizeof(nboard));
swap(nboard[ny][nx], nboard[cur.y][cur.x]);//swap해주고
ll nextcode = hashcode(nboard);//다음 움직일 장소의 해쉬코드를 찾음
if (visit.count(nextcode)==0){//방문한적있는지
visit.insert(nextcode);
q.push({ nboard, cur.cnt + 1 });
}
}
}
}
return -1;
}
int main(){
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++){
cin >> map[i][j];
}
}
cout << bfs() << "\n";
}
|
cs |
궁금한점 혹은 모르는점 혹은 어떤질문이든 괜찮습니다.
댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 20057 마법사 상어와 토네이도 (0) | 2021.02.10 |
|---|---|
| 백준 3190 뱀 (0) | 2021.02.10 |
| 벡즌 1929 소수 구하기 (0) | 2021.01.01 |
| 백준 16938 캠프 준비 (0) | 2020.12.31 |
| 백준 9944 NxM 보드 완주하기 (0) | 2020.12.31 |
