본문 바로가기
컴퓨터/Problem Solving

(BOJ, 1525) 퍼즐

by 빵케잌 2020. 1. 28.

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

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