글 읽기 - [10216] 제가 시간복잡도 계산하는법이 틀린건가요??

san9407 5년 전 0

처음 풀었을땐 bfs하고 dfs로 했을땐 dfs때문인지 int때문인지 잘은 모르겠지만 메모리초과가 나서

숫자가 5000이하라 short 변수로 풀었습니다.

4방향 탐색하면서 코스트만큼 갈수있는곳 다 true로 바꿔주고

한번더 bfs탐색하면서 그룹 찾는걸로 했는데요

5001 * 5001 * 4 * 2 하면 2억이던데 2억이면 대충 2초아닌가요??

제가 시간복잡도를 잘못생각하고 있는걸까요??

#include <cstdio>
#include<vector>
#include<queue>
using namespace std;
#pragma warning(disable:4996)

int T, N;
short arr[5001][5001];
bool visit[5001][5001];
int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };
queue<pair<short,pair<short,short>>> q;

void bfs()
{
	while (!q.empty())
	{
		short x = q.front().second.first;
		short y = q.front().second.second;
		short cost = q.front().first;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			short rx = x + dx[i];
			short ry = y + dy[i];
			if (rx<0 || ry<0 || rx>5000 || ry>5000 || visit[rx][ry] == true|| cost<=0)
			{
				continue;
			}
			else
			{
				visit[rx][ry] = true;
				q.push({ cost - 1,{ rx,ry } });
			}
		}
	}
}

void bfs2(int tx, int ty)
{
	queue<pair<short, short>> q2;
	q2.push({ tx,ty });
	while (!q2.empty())
	{
		short x = q2.front().first;
		short y = q2.front().second;
		q2.pop();
		for (int i = 0; i < 4; i++)
		{
			short rx = x + dx[i];
			short ry = y + dy[i];
			if (rx<0 || ry<0 || rx>5000 || ry>5000 || visit[rx][ry] == false)
			{
				continue;
			}
			else
			{
				visit[rx][ry] = false;
				q2.push({ rx,ry });
			}
		}

	}
}

int main() 
{
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &N);
		for(int i=0;i<N;i++)
		{
			short x, y, r;
			scanf("%hd %hd %hd", &x, &y, &r);
			arr[x][y] = r;
			q.push({ r,{x,y} });
			visit[x][y] = true;
		}
		bfs();
		int ans = 0;
		for (int i = 0; i < 5001; i++)
		{
			for (int j = 0; j < 5001; j++)
			{
				if (visit[i][j] == true)
				{
					ans++;
					visit[i][j] = false;
					bfs2(i,j);
				}
			}
		}
		printf("%d\n", ans);
		for (int i = 0; i < 5001; i++)
		{
			for (int j = 0; j < 5001; j++)
			{
				visit[i][j] = false;
			}
		}
	}
	return 0;
}

djm03178 5년 전 1

한 개의 테스트에 2초면 TC의 수가 10개만 돼도 20초입니다.

물론 이 문제의 데이터가 그렇게 빡세지는 않지만, 요구하는 시간복잡도는 대략 O(N^2) 정도 되는 것 같습니다. 좌표가 아니라, 진영의 수입니다.

san9407 5년 전 0

아 그러고보니 테스트 케이스가 주어졌네요 ㅜㅜ;

감사합니다 다른방법 찾아볼게요

jh05013 5년 전 1

시간복잡도 이외에도 몇 가지 문제가 있습니다.

우선 두 진영 A와 B의 시야가 겹친다면 bfs함수는 제대로 true로 바꾸지 못할 것입니다. B의 시야를 갱신하다가 A의 시야에 부딪혀 visit[rx][ry] = true로 판단하기 때문입니다. 이걸 해결하려고 하면 O(N^2R)이 되어서 무조건 시간초과가 납니다.

애초에 이렇게 하면 다이아몬드 모양으로 시야가 퍼지는데, 실제 시야는 원입니다. 따라서 이렇게 풀 수 없습니다.

san9407 5년 전 0

감사합니다!!

다른방법으로도 해볼게요

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

문제

문제

출처

ICPC

[10216] 제가 시간복잡도 계산하는법이 틀린건가요??

san9407 5년 전 0

djm03178 5년 전 1

san9407 5년 전 0

jh05013 5년 전 1

san9407 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말