글 읽기 - 시간초과 질문(방문한 퍼즐형태 처리)

rlatjrdnjs 6년 전 0

condition()함수 안에서 find_0 함수로 0의 위치를 찾고 이동 가능한지 검사를 하며 BFS로 모든 경우를 탐색하는데 방문처리를 너무 느리게 해서 시간초과가 나는것 같습니다.

char v[9][9].....[9]의 형태로 방문을 표시하기에는 9^9byte로 메로리를 매우 많이 차지하기 때문에

큐(int q[QSIZE]) 의 모든 데이터를 검사하며 이미 방문한 형태인지를 검사하였습니다.

제출하고 나니 시간초과가 뜨네요 다른 방법이 있을까요?

#include <stdio.h>
#define QSIZE 362880

int q[QSIZE];
int dis[QSIZE];
int head, tail;
int s, d = 123456780;

void eq(int in, int level) {
	q[tail] = in;
	dis[tail++] = level;
}
void dq(int *des, int *level) {
	*des = q[head];
	*level = (dis[head++] + 1);
}
int find_0(int in) {
	int a = 10;
	int b, rt = 1;
	while (in > 0) {
		b = in%a;
		if (b == 0) {
			return rt;
		}
		in = in / a;

		rt++;
	}
	return 9;
}
int condition(int in, int dir, int level) {
	int pos = find_0(in);
	int buf_in = in, swap_buf, swap_buf2, buf;
	//printf("in:%d, pos:%d,dir:%d\n",in,pos,dir);
	if (dir == 0) {
		if (pos == 7 || pos == 8 || pos == 9) {
			return 0;
		}
		for (int i = 0; i < pos + 2; ++i) {
			buf_in /= 10;
		}
		swap_buf = buf_in % 10;
		for (int i = 0; i < pos + 2; ++i) {
			swap_buf *= 10;
		}
		in -= swap_buf;

		in += (swap_buf / 1000);

		if (in == d) {
			return 1;
		}
		for (int i = 0; i < tail; ++i) {
			if (in == q[i]) {
				return 0;
			}
		}
		//printf("in:%d, in:%d, dir:%d, level:%d\n", in, in, dir, level);
		eq(in, level);
	}
	else if (dir == 1) {
		if (pos == 1 || pos == 4 || pos == 7) {
			return 0;
		}
		for (int i = 0; i < pos - 2; ++i) {
			buf_in /= 10;
		}
		swap_buf = buf_in % 10;
		for (int i = 0; i < pos - 2; ++i) {
			swap_buf *= 10;
		}
		in -= swap_buf;
		in += (swap_buf * 10);

		if (in == d) {
			return 1;
		}
		for (int i = 0; i < tail; ++i) {
			if (in == q[i]) {
				return 0;
			}
		}
		//	printf("in:%d, in:%d, dir:%d, level:%d\n", in, in, dir, level);
		eq(in, level);
	}
	else if (dir == 2) {
		if (pos == 1 || pos == 2 || pos == 3) {
			return 0;
		}
		for (int i = 0; i < pos - 4; ++i) {
			buf_in /= 10;
		}
		swap_buf = buf_in % 10;
		for (int i = 0; i < pos - 4; ++i) {
			swap_buf *= 10;
		}
		in -= swap_buf;

		in += (swap_buf * 1000);

		if (in == d) {
			return 1;
		}
		for (int i = 0; i < tail; ++i) {
			if (in == q[i]) {
				return 0;
			}
		}
		//printf("in:%d, in:%d, dir:%d, level:%d\n", in, in, dir, level);
		eq(in, level);
	}
	else if (dir == 3) {
		if (pos == 3 || pos == 6 || pos == 9) {
			return 0;
		}
		for (int i = 0; i < pos; ++i) {
			buf_in /= 10;
		}
		swap_buf = buf_in % 10;
		for (int i = 0; i < pos; ++i) {
			swap_buf *= 10;
		}
		in -= swap_buf;
		in += (swap_buf / 10);

		if (in == d) {
			return 1;
		}
		for (int i = 0; i < tail; ++i) {
			if (in == q[i]) {
				return 0;
			}
		}
		//printf("in:%d, in:%d, dir:%d, level:%d\n", in, in, dir, level);
		eq(in, level);
	}
	return 0;
}
int BFS(void) {
	int buf, level;
	eq(s, 0);
	while (head != tail) {
		dq(&buf, &level);
		for (int k = 0; k < 4; ++k) {
			if (condition(buf, k, level)) {
				return level;
			}
		}
	}
	return -1;
}
int main(void) {
	int map[3][3];
	int x, y, p = 1, count = 1;
	int ans;
	for (int i = 0; i < 3; ++i) {
		for (int j = 0; j < 3; ++j) {
			scanf("%d", &map[i][j]);
		}
	}
	for (int y = 2; y >= 0; --y) {
		for (int x = 2; x >= 0; --x) {
			p *= 10;
			s += (map[y][x] * p);
		}
	}
	s /= 10;
	ans = BFS();
	printf("%d\n", ans);
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 질문(방문한 퍼즐형태 처리)

rlatjrdnjs 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말