(BOJ, 1525) 퍼즐

로직은 한참 전에 맞춰놓고, 장시간 오답 이유를 못찾아서 헤맸던 문제

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로 넘어가는 식으로 해야하는데 힙으로 하면 그게 가능하고 속도도 더 빠를 것임.