글 읽기 - 시간초과가 왜 나나요?

okm1172 1년 전 0

우선순위 큐에 pair<벽 부수면 -1 안부수면 0 , pair < x좌표 , y좌표 >> 로 놓고 bfs돌리는 풀이를 했는데, 시간초과가 납니다.

N * M * Log(N*M) 아닌가요?

놓치고 있는 부분이 있다면 알려주시면 감사하겠습니다 ㅜ.ㅜ

#include <iostream>
#include <queue>
#include <string>

using namespace std;
priority_queue <pair< int, pair<int, int>>> xy;

int data_[1004][1004];
int data_2[1004][1004];
//data_2는 개수 data_는 입력 데이터
int n, m;
void bfs(int x,int y)
{
	int check2 = xy.top().first;
	xy.pop();
	if (x == 0 || x > n || y == 0 || y > m)
		return;
	if (data_[x + 1][y] == 1)
	{
		if (check2 == 0)
		{
			if (data_2[x + 1][y] > data_2[x][y] + 1 || data_2[x+1][y]==0)
			{
				data_2[x + 1][y] = data_2[x][y] + 1;
				xy.push(make_pair(-1, make_pair(x + 1, y)));
			}
		}
	}
	if (data_[x - 1][y] == 1)
	{
		if (check2 == 0)
		{
			if (data_2[x - 1][y] > data_2[x][y] + 1||data_2[x-1][y]==0)
			{
				data_2[x - 1][y] = data_2[x][y] + 1;
				xy.push(make_pair(-1, make_pair(x -1, y)));
			}
		}
	}
	if (data_[x][y + 1] == 1)
	{
		if (check2 == 0)
			if (data_2[x][y+1] > data_2[x][y] + 1 || data_2[x][y+1]==0)
			{
				data_2[x][y + 1] = data_2[x][y] + 1;
				xy.push(make_pair(-1, make_pair(x, y+1)));
			}
	}
	if (data_[x][y - 1] == 1)
	{
		if (check2 == 0)
			if (data_2[x][y-1] > data_2[x][y] + 1 || data_2[x][y-1]==0)
			{
				data_2[x][y - 1] = data_2[x][y] + 1;
				xy.push(make_pair(-1, make_pair(x, y-1)));
			}
	}
	if (data_[x + 1][y] == 0)
	{
		if (check2 == -1)
		{
			if (data_2[x][y] + 1 < data_2[x + 1][y] || data_2[x+1][y]==0)
			{
				data_2[x + 1][y] = data_2[x][y] + 1;
				xy.push(make_pair(-1, make_pair(x + 1, y)));
			}
		}
		else
		{
			if (data_2[x][y] + 1 < data_2[x + 1][y] || data_2[x + 1][y] == 0)
			{
				data_2[x + 1][y] = data_2[x][y] + 1;
				xy.push(make_pair(0, make_pair(x + 1, y)));
			}
		}
	}
	if (data_[x][y + 1] == 0)
	{
		if (check2 == -1)
		{
			if (data_2[x][y] + 1 < data_2[x][y+1] || data_2[x][y+1]==0)
			{
				data_2[x][y + 1] = data_2[x][y] + 1;
				xy.push(make_pair(-1, make_pair(x, y+1)));
			}
		}
		else
		{
			if (data_2[x][y] + 1 < data_2[x][y+1] || data_2[x][y + 1] == 0)
			{
				data_2[x][y + 1] = data_2[x][y] + 1;
				xy.push(make_pair(0, make_pair(x, y+1)));
			}
		}
	}
	if (data_[x - 1][y] == 0)
	{
		if (check2 == -1)
		{
			if (data_2[x][y] + 1 < data_2[x -1 ][y] || data_2[x-1][y]==0)
			{
				data_2[x - 1][y] = data_2[x][y] + 1;
				xy.push(make_pair(-1, make_pair(x - 1, y)));
			}
		}
		else
		{
			if (data_2[x][y] + 1 < data_2[x - 1][y] || data_2[x - 1][y] == 0)
			{
				data_2[x - 1][y] = data_2[x][y] + 1;
				xy.push(make_pair(0, make_pair(x - 1, y)));
			}
		}
	}
	if (data_[x][y - 1] == 0)
	{
		if (check2 == -1)
		{
			if (data_2[x][y] + 1 < data_2[x][y-1] || data_2[x][y-1] == 0)
			{
				data_2[x][y - 1] = data_2[x][y] + 1;
				xy.push(make_pair(-1, make_pair(x, y-1)));
			}
		}
		else
		{
			if (data_2[x][y] + 1 < data_2[x][y - 1] || data_2[x][y-1] == 0)
			{
				data_2[x][y - 1] = data_2[x][y] + 1;
				xy.push(make_pair(0, make_pair(x, y-1)));
			}
		}
	}
	if (xy.empty())
	{
		return;
	}
	int xx = xy.top().second.first, yy = xy.top().second.second;
	bfs(xx, yy);
}
int main()
{
	string input;
	char qq;
	cin >> n >> m;
	for (int i = 0; i <=n + 1; i++)
	{
		for (int j = 0; j <= n + 1; j++)
		{
			data_[i][j] = 2;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> input;
		for (int j = 1; j <= m; j++)
		{
			data_[i][j] = input[j-1]=='0' ? 0 : 1;
		}
	}
	data_2[1][1] = 1;
	xy.push(make_pair(0,make_pair(1, 1)));
	bfs(1, 1);
	cout << (data_2[n][m]==0 ? -1 : data_2[n][m]);
	return 0;
}

zenith82114 1년 전 0

BFS는 재귀호출을 하면 안됩니다.

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

문제

문제

출처

ICPC

시간초과가 왜 나나요?

okm1172 1년 전 0

zenith82114 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말