글 읽기 - bfs 복잡도 질문

jsjsjs0775 5년 전 0

bfs로 문제를 풀어보았는데 정답은 맞췄지만

복잡도계산을 어떻게 해야되는지 잘모르겠어서 질문드립니다,,

제 생각에 복잡도가 bfs가 V^2(인접행렬)이므로

'1번의 인구이동'에서 일어나는 복잡도는 약 2500*2500 라고 생각되는데요

조건에 인구이동발생 횟수가 2000번보다 작은 입력만 주어진다면

2500*2500*2000의 복잡도를 가져서 12,500,000,000 의 결과가 나오는데 이러면 시간초과가 나오지 않나요?

복잡도계산을 어떻게해야 올바르게 나올까요?,,,

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

queue<pair<int, int> >q;
vector<pair<int, int>> v;

int dx[4] = { 1,0,-1,0};
int dy[4] = { 0,1,0,-1};
int map[51][51];
int vcnt;

int main(void)
{
	int n, l, r;
	cin >> n >> l >> r;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> map[i][j];
		}
	}

	int swi = 0;

	while (1)
	{
		int visit[51][51] = {};
		int ncnt[2501][2] = {};

		swi = 0;

		int x, y, nx, ny, diff;
		int cnt = 0;
		int swi = 0;

		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (visit[i][j] != 0) continue;
				cnt++;
				q.push({ j,i });

				while (!q.empty())
				{
					x = q.front().first;
					y = q.front().second;
					visit[y][x] = cnt;
					ncnt[cnt][0]++;
					ncnt[cnt][1] += map[y][x];
					q.pop();

					//cout << "x:" << x << " y:" << y << endl;
					if (i != y || j != x) swi = 1;
					for (int k = 0; k < 4; k++)
					{
						nx = x + dx[k];
						ny = y + dy[k];
						if (nx<1 || nx>n || ny<1 || ny>n) continue;
						if (visit[ny][nx] != 0) continue;
						diff = abs(map[ny][nx] - map[y][x]);
						if (diff >= l && diff <= r)
						{
							q.push({ nx,ny });
							visit[ny][nx] = cnt;
						}
					}
				}
			}
		}
		if (swi == 0) break;

		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (visit[i][j] != 0)
				{
					map[i][j] = ncnt[visit[i][j]][1] / ncnt[visit[i][j]][0];
				}
			}
		}

		if (swi == 0) break;

		/*cout << endl;
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				cout << map[i][j] << " ";
			}
			cout << endl;
		}*/

		vcnt++;
	}

	cout << vcnt;
}

pda_pro12 5년 전 0

결국 인구이동시키는 시뮬레이션을 할수록 인구이동이 발생하는 확률이 줄어든다고 생각하시면 이해하기 편합니다.

(2500(모든칸을 한번씩만 방문하게 되므로 50*50)+(하나의 케이스당 발생하는것이므로 합연산으로 연산해줍니다)2500(인구이동을 각칸마다 계산해주는 과정)) * (while문을 도는 횟수 )

이렇게인데 결국 위의 작성하신 코드대로라면 사실 bfs를 도는과정에서 발생하는 상수시간 복잡도 O(4)도 무시할수 없이 커지게 되서 불가능하게 됩니다.

하지만 인구이동을 하는과정에서 각 칸의 편차가 점점 줄어든다고 생각하시면 절대 터지지 않을 겁니다.

jsjsjs0775 5년 전 0

아.. 편차가 줄어들면서 bfs로 확산될 노드가 줄어들면서 복잡도가 줄어드는군요 감사합니다!!

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

문제

문제

출처

ICPC

bfs 복잡도 질문

jsjsjs0775 5년 전 0

pda_pro12 5년 전 0

jsjsjs0775 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말