로직은 한참 전에 맞춰놓고, 장시간 오답 이유를 못찾아서 헤맸던 문제
1. BFS 시, next state의 visited 체크는 당연하지만, init state를 빼먹음.
2. visited의 값을 0을 non-visited로 하면 안되는 문제임. 한번도 안 바꿔도 정답인 경우와 non-visited가 구분이 안되기 때문.
3. 해시 구현 시 바보같이 key 구할 때 a 훼손시켜놓고 visited[].val에 그걸 그대로 쓰고 있었다..
4. 퍼즐 인덱스 2->3 과 같은 경우는 걸러야하는 case인데 0~8안에 들어오기만 하면 올바른 전환으로 안일하게 생각함.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int puzzle;
int ans;
int dir[4] = { 1, -1, 3,-3 };
struct st {
int val;
int cnt;
}queue[400000]; // 9! == 362880
int wp, rp;
struct visit{
int val;
int cnt;
}visited[800000];
int get_hash(int a) {
unsigned int key = 0;
int b = a;
while (b) {
key = key * 31 + b%10;
key %= 800000;
b /= 10;
}
while (visited[key].val !=a && visited[key].val!=0)key++;
if (visited[key].val == 0) {
visited[key].val = a;
}
return key;
}
int get_zeroindex(int a) {
for (int i = 8; i >= 0; i--) {
if (a % 10 == 0)return i;
a /= 10;
}
return -1;
}
int swap(int val, int index1, int index2) {
char s[9];
int ret = 0;
for (int i = 8; i >= 0; i--) {
s[i] = val % 10;
val /= 10;
}
s[index1] ^= s[index2] ^= s[index1] ^= s[index2];
for (int i = 0; i < 9; i++) {
ret = ret * 10 + s[i];
}
return ret;
}
void bfs() {
struct st t = { puzzle,0 };
int key = get_hash(puzzle);
visited[key].cnt = t.cnt;
queue[wp++] = t;
struct st cur;
while (rp < wp) {
cur = queue[rp++];
int zero_index = get_zeroindex(cur.val);
for (int j = 0; j < 4; j++) {
int change_point = zero_index + dir[j];
if (zero_index % 3 == 2 && change_point == zero_index + 1)continue;
if (zero_index % 3 == 0 && change_point == zero_index - 1)continue;
if (change_point >= 0 && change_point < 9) {
struct st next = { 0, cur.cnt + 1 };
next.val = swap(cur.val, zero_index, change_point);
int key = get_hash(next.val);
if (visited[key].cnt==-1 || visited[key].cnt > next.cnt) {
queue[wp++] = next;
visited[key].cnt = next.cnt;
}
}
}
}
}
int main() {
int N;
for (int i = 0; i < 9; i++) {
scanf("%d", &N);
puzzle = puzzle * 10 + N;
}
for (register int i = 0; i < 800000; i++)
visited[i].cnt = -1;
ans = 123456780;
bfs();
int a = visited[get_hash(ans)].cnt;
printf("%d",a);
return 0;
}
위의 방식대로 해도 해결되지만 사실 큐로하면 진정한 bfs가 아닙니다.. depth가 적은 state가 모두 진행 되고 다음 depth로 넘어가는 식으로 해야하는데 힙으로 하면 그게 가능하고 속도도 더 빠를 것임.
'컴퓨터 > Problem Solving' 카테고리의 다른 글
11.16 ex(decode 풀이) (0) | 2020.03.18 |
---|---|
200201 ex (0) | 2020.02.03 |
(BOJ, 1062) 가르침 (0) | 2020.01.28 |
(BOJ, 1806) 부분합 (0) | 2020.01.27 |
(BOJ, 5052) 전화번호 목록 (0) | 2020.01.27 |