글 읽기 - 시간초과의 원인을 찾는데 도움이 필요합니다.

shin0343 5년 전 0

BFS를 이용하여 구현했고, 1이 저장된 토마토 판의 인덱스를 큐로 저장했는데 도대체 어느 부분에서 시간 초과가 발생하는지 찾기가 힘듭니다.. 같이 봐주실수 있을까요?

#include <iostream>
#include <queue>
using namespace std;

int n, m, ans = 999999999;
int board[1000][1000];
bool chk[1000][1000];
queue<pair<int, int> > cacheQ;

class Pos //큐 원소
{
public:
	Pos(int i_c,int i_l,int i_cnt)
	{
		col = i_c;
		low = i_l;
		cnt = i_cnt;
	}
	int col; //행 번호
	int low; //열 번호
	int cnt; //지나온 지점 카운트
};

bool promising(int col, int low) //유망한 지점인지 확인 함수
{
	if (col < 0 || low < 0 || col >= m || low >= n)
	{
		return false;
	}
	if (board[col][low] == -1)
	{
		return false;
	}
	if (chk[col][low] == true)
	{
		return false;
	}

	return true;
}

bool isAns()
{
	bool b_pos = true;

	for (int i = 0; i <= m - 1; i++)
	{
		for (int j = 0; j <= n - 1; j++)
		{
			if (board[i][j] == -1)
			{
				continue;
			}
			else if (chk[i][j] == 0)
			{
				b_pos = false;
			}
		}
	}

	return b_pos;
}

void bfs() //BFS 본래 함수
{
	queue<Pos> q;
	while (!cacheQ.empty())
	{
		q.push(Pos(cacheQ.front().first, cacheQ.front().second, 0));
		cacheQ.pop();
	}

	while (!q.empty())
	{
		Pos cur_Pos = q.front();
		q.pop();
		//cout << "q is not empty! col:" << cur_Pos.col << ", low" << cur_Pos.low << endl;

		if (promising(cur_Pos.col,cur_Pos.low))
		{
			//cout << "유망하다! col:" << cur_Pos.col << ", low: " << cur_Pos.low << ", cnt: " << cur_Pos.cnt<< endl;
			chk[cur_Pos.col][cur_Pos.low] = true;

			if (board[cur_Pos.col][cur_Pos.low] == 0)
			{
				cur_Pos.cnt++;
			}

			if (isAns())
			{
				ans = cur_Pos.cnt < ans ? cur_Pos.cnt : ans;
				//cout << "ans! col:" << cur_Pos.col << ", low: " << cur_Pos.low << endl;
			}
			else
			{
				q.push(Pos(cur_Pos.col - 1, cur_Pos.low, cur_Pos.cnt));
				q.push(Pos(cur_Pos.col + 1, cur_Pos.low, cur_Pos.cnt));
				q.push(Pos(cur_Pos.col, cur_Pos.low - 1, cur_Pos.cnt));
				q.push(Pos(cur_Pos.col, cur_Pos.low + 1, cur_Pos.cnt));
			}
		}
		else
		{
			continue;
		}
	}
}

int main()
{
	scanf("%d %d", &n, &m);

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> board[i][j];
			if (board[i][j] == 1)
			{
				cacheQ.push({ i, j });
			}
		}
	}
	/*for (int i = 0; i < m; i++)
	{
	for (int j = 0; j < n; j++)
	{
	cout << board[i][j];
	}cout << '\n';
	}*/

	bfs();


	if (ans == 999999999)
	{
		ans = -1;
	}
	cout << ans;

	return 0;
}

shin0343 5년 전 1

말씀하신대로 해봤지만 2%에서 시간초과가 나는군요.. 조금더 연구해보도록 하겠습니다.

#include <iostream>
#include <queue>
using namespace std;

int n, m, ans = 999999999;
int board[1000][1000];
bool chk[1000][1000];
queue<pair<int, int> > cacheQ;

class Pos //큐 원소
{
public:
	Pos(int i_c, int i_l, int i_cnt)
	{
		col = i_c;
		low = i_l;
		cnt = i_cnt;
	}
	int col; //행 번호
	int low; //열 번호
	int cnt; //지나온 지점 카운트
};

bool promising(int col, int low) //유망한 지점인지 확인 함수
{
	if (col < 0 || low < 0 || col >= m || low >= n)
	{
		return false;
	}
	if (board[col][low] == -1)
	{
		return false;
	}
	if (chk[col][low] == true)
	{
		return false;
	}

	return true;
}

bool isAns()
{
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (board[i][j] == -1)
			{
				continue;
			}
			if (board[i][j] == 0 && chk[i][j] == false)
			{
				return false;
			}
		}
	}

	return true;
}

void bfs() //BFS 본래 함수
{
	queue<Pos> q;
	while (!cacheQ.empty())
	{
		q.push(Pos(cacheQ.front().first, cacheQ.front().second, 0));
		cacheQ.pop();
	}

	while (!q.empty())
	{
		Pos cur_Pos = q.front();
		q.pop();
		//cout << "q is not empty! col:" << cur_Pos.col << ", low" << cur_Pos.low << endl;

		//if (promising(cur_Pos.col, cur_Pos.low))
		{
			//chk[cur_Pos.col][cur_Pos.low] = true;

			if (board[cur_Pos.col][cur_Pos.low] == 0)
			{
				cur_Pos.cnt++;
			}
			//cout << "유망하다! col:" << cur_Pos.col << ", low: " << cur_Pos.low << ", cnt: " << cur_Pos.cnt << endl;


			if (isAns())
			{
				ans = cur_Pos.cnt;
				//ans = cur_Pos.cnt < ans ? cur_Pos.cnt : ans;
				//cout << "ans! col:" << cur_Pos.col << ", low: " << cur_Pos.low << endl;
			}
			else
			{
				if (promising(cur_Pos.col - 1, cur_Pos.low))
				{
					chk[cur_Pos.col - 1][cur_Pos.low] = true;
					q.push(Pos(cur_Pos.col - 1, cur_Pos.low, cur_Pos.cnt));
				}
				if (promising(cur_Pos.col + 1, cur_Pos.low))
				{
					chk[cur_Pos.col + 1][cur_Pos.low] = true;
					q.push(Pos(cur_Pos.col + 1, cur_Pos.low, cur_Pos.cnt));
				}
				if (promising(cur_Pos.col, cur_Pos.low - 1))
				{
					chk[cur_Pos.col][cur_Pos.low - 1] = true;
					q.push(Pos(cur_Pos.col, cur_Pos.low - 1, cur_Pos.cnt));
				}
				if (promising(cur_Pos.col, cur_Pos.low + 1))
				{
					chk[cur_Pos.col][cur_Pos.low + 1] = true;
					q.push(Pos(cur_Pos.col, cur_Pos.low + 1, cur_Pos.cnt));
				}
			}
		}
	}
}

int main()
{
	scanf("%d %d", &n, &m);

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			scanf("%d", &board[i][j]);
			//cin >> board[i][j];
			if (board[i][j] == 1)
			{
				cacheQ.push({ i, j });
			}
		}
	}
	/*for (int i = 0; i < m; i++)
	{
	for (int j = 0; j < n; j++)
	{
	cout << board[i][j];
	}cout << '\n';
	}*/

	bfs();


	if (ans == 999999999)
	{
		ans = -1;
	}
	//cout << ans;
	printf("%d", ans);

	return 0;
}

shin0343 5년 전 1

isAns함수의 전수 호출로 인해서 시간초과가 발생하는 것으로 생각되어 해당 부분 수정해보니 정답이라고 나오는군요!!

더불어 말씀하신 내용 적용하니 메모리와 시간이 감소하여 최적화된 코드를 작성할 수 있었습니다 감사합니다~

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

문제

문제

출처

ICPC

시간초과의 원인을 찾는데 도움이 필요합니다.

shin0343 5년 전 0

shin0343 5년 전 1

shin0343 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말