글 읽기 - 시간 초과 어떤 조건이 있어야 할까요

songgj123 7년 전 0

DP로 풀었더니 시간 초과가 나서

BFS로 다시 풀었는데 또 시간 초과가 나오네요

기본적인 BFS와 같습니다.

첫 줄을 탐색하며 1이 있는 지점을 찾아 출발합니다.

한 번의 출발에서 다시 방문하지 않도록, visited 배열을 선언해 걸음 수를 저장했습니다.

다음 출발 때도 visited 배열은 계속 유지해서

다음 출발 이후에 그 지점을 방문했을 때, 걸음 수와 visited 배열을 비교해 지점을 queue에 저장할지 정합니다.

더 줄일 방법이 생각이 안나서 그러는데 어떤 식으로 시간을 줄일 수 있을까요??

한 가지 생각해 본 것은 어떤 path가 조건에 맞지 않으면,

path 내의 지점들을 다음부터 방문하지 않도록 하는 방법입니다.

조언해주시면 감사하겠습니다.

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

const int RULE_MAX = 10;
const int MAX = 1000;
const int INF = 987654321;

int dx[RULE_MAX];
int dy[RULE_MAX];
bool arr[MAX][MAX];
int visited[MAX][MAX];
int r, c;
int n;
queue<pair<int, int>> Q;

bool allowXY(int x, int y, int d)
{
	int nx = x + dx[d];
	int ny = y + dy[d];

	if(nx < 0 || nx >= r || ny < 0 || ny >= c)
	{
		return false;
	}
	else if(arr[nx][ny] == false)
	{
		return false;
	}
	return true;
}

void Qinit()
{
	while(!Q.empty())
	{
		Q.pop();
	}
}

int BFS(int x, int y)
{
	int cnt = 0;

	Qinit();

	Q.push(make_pair(x, y));
	visited[x][y] = cnt;

	while(1)
	{
		x = Q.front().first;
		y = Q.front().second;
		cnt = visited[x][y];
		cnt++;
		Q.pop();

		for(int i = 0; i < n; i++)
		{
			if(allowXY(x, y, i) && ((visited[x + dx[i]][y + dy[i]] == -1) || (visited[x + dx[i]][y + dy[i]] > cnt)))
			{
				Q.push(make_pair(x + dx[i], y + dy[i]));
				visited[x + dx[i]][y + dy[i]] = cnt;

				if(x + dx[i] == r - 1)
				{
					return cnt;
				}
			}
		}

		if(Q.empty())
		{
			break;
		}
	}
	return INF;
}

int solve()
{
	int ret = INF;

	memset(visited, -1, sizeof(visited));

	for(int i = 0; i < c; i++)
	{
		if(arr[0][i] == 1)
		{
			ret = min(ret, BFS(0, i));
		}
	}
	if(ret == INF)
	{
		return -1;
	}
	return ret;
}

int main()
{
	scanf("%d %d", &r, &c);

	for(int i = 0; i < r; i++)
	{
		for(int j = 0; j < c; j++)
		{
			scanf("%d", &arr[i][j]);
		}
	}

	scanf("%d", &n);

	for(int i = 0; i < n; i++)
	{
		scanf("%d %d", &dx[i], &dy[i]);
	}
	printf("%d", solve());

	return 0;
}

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

문제

문제

출처

ICPC

시간 초과 어떤 조건이 있어야 할까요

songgj123 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말