글 읽기 - 14868번 문명) 맞은 코드보다 더 빠른 코드가 왜 시간초과날까요?

edenooo 5년 전 0

1~91줄에 있는 첫 번째 AC 받은 코드고

100~225줄에 있는 두 번째 코드가 70%쯤에서 반복적으로 시간 초과를 받은 코드입니다.

2000 2

1 1

2000 2000

이런 입력을 넣었을 때 제 컴퓨터에선 첫 번째 코드가 두 번째 코드보다 대략 10초 늦게 동작합니다.

이것처럼 큰 입력을 몇 개 만들어 봤는데 모두 두 번째 코드가 더 빨랐고, 저는 두 번째 코드가 더 빠르겠다고 판단하고 속도를 개선하려고 몇 시간을 소비했는데 정작 첫 번째 코드가 420ms로 여유롭게 통과하는 걸 보니 허무하네요...

어째서 제 컴퓨터에서 테스트한 결과와 다르게 첫 번째 코드가 시간 제한에 걸리지 않으면서 두 번째 코드는 시간 제한에 걸리는지 알려주세요 ㅠㅠ

#include<stdio.h>
#include<vector>
#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;

#define INF 987654321
#define ull unsigned long long

int N, M, progress, hx, hy, nx, ny, year, i, j, t1, t2;
int g[2000][2000];
bool chk[2000][2000];
int parent[100001];
short Rank[100001];
queue<pair<int, int> > q, qq;
int dir[4][2] = { {0,-1}, {0,1}, {-1,0}, {1,0} };

int find(int n)
{
	if (n == parent[n]) return n;
	return parent[n] = find(parent[n]);
}

void merge(int a, int b)
{
	a = find(a), b = find(b);
	if (Rank[a] > Rank[b]) swap(a, b);
	parent[a] = b;
	if (Rank[a] == Rank[b]) Rank[b]++;
}

int BFS()
{
	year = 0;

	while (1)
	{
		while (!q.empty())
		{
			hx = q.front().first, hy = q.front().second;
			qq.push(q.front());
			q.pop();

			for (i = 0; i < 4; i++)
			{
				nx = hx + dir[i][0], ny = hy + dir[i][1];
				if (nx < 0 || ny < 0 || nx >= N || ny >= N || g[nx][ny]==0 || find(g[hx][hy]) == find(g[nx][ny])) continue;

				merge(g[hx][hy], g[nx][ny]);
				progress--;
				if (progress == 1) return year;
			}
		}

		while (!qq.empty())
		{
			hx = qq.front().first, hy = qq.front().second;
			qq.pop();

			for (i = 0; i < 4; i++)
			{
				nx = hx + dir[i][0], ny = hy + dir[i][1];
				if (nx < 0 || ny < 0 || nx >= N || ny >= N || g[nx][ny] != 0) continue;

				q.push(make_pair(nx, ny));
				g[nx][ny] = g[hx][hy];
			}
		}

		year++;
	}
}

int main()
{
	scanf("%d %d", &N, &M);
	for (i = 1; i <= M; i++)
	{
		scanf("%d %d", &t1, &t2);
		g[t1 - 1][t2 - 1] = i;
		q.push(make_pair(t1 - 1, t2 - 1));
		parent[i] = i;
	}

	progress = M;

	printf("%d", BFS());
	return 0;
}

/*

이 아래부터는 두 번째 코드입니다


*/

#include<stdio.h>
#include<vector>
#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;

#define INF 987654321
#define ull unsigned long long

int N, M, progress, hx, hy, nx, ny, nnx, nny, day, i, j;
int g[2000][2000];
bool chk[2000][2000];
int parent[100001];
short Rank[100001];
vector<pair<int, int> > start;
queue<pair<int, pair<int, int> > > q; //day x y
int dir[4][2] = { {0,-1}, {0,1}, {-1,0}, {1,0} };

int find(int n)
{
	if (n == parent[n]) return n;
	return parent[n] = find(parent[n]);
}

void merge(int a, int b)
{
	a = find(a), b = find(b);
	if (Rank[a] > Rank[b]) swap(a, b);
	parent[a] = b;
	if (Rank[a] == Rank[b]) Rank[b]++;
}

bool checkOne()
{
	queue<pair<int, int> > q2;
	q2.push(make_pair(q.front().second.first, q.front().second.second));

	while (!q2.empty())
	{
		hx = q2.front().first, hy = q2.front().second;
		q2.pop();

		chk[hx][hy] = true;

		for (i = 0; i < 4; i++)
		{
			nx = hx + dir[i][0], ny = hy + dir[i][1];
			if (nx < 0 || ny < 0 || nx >= N || ny >= N || g[nx][ny] == 0 || chk[nx][ny] == true) continue;

			q2.push(make_pair(nx, ny));
		}
	}
	
	for (i = 0; i < M; i++)
	{
		hx = start[i].first, hy = start[i].second;
		if (chk[hx][hy] == false) return false;
	}
	return true;
}

int BFS()
{
	int Max = 0;

	while (1)
	{
		hx = q.front().second.first, hy = q.front().second.second;
		day = q.front().first;
		q.pop();

		for (i = 0; i < 4; i++)
		{
			nx = hx + dir[i][0], ny = hy + dir[i][1];
			if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;

			if (g[nx][ny] == 0)
			{
				q.push(make_pair(day+1, make_pair(nx, ny)));
				g[nx][ny] = g[hx][hy];

				for (j = 0; j < 4; j++)
				{
					nnx = nx + dir[j][0], nny = ny + dir[j][1];
					if (nnx < 0 || nny < 0 || nnx >= N || nny >= N || g[nnx][nny] == 0 || find(g[nx][ny]) == find(g[nnx][nny])) continue;

					merge(g[nx][ny], g[nnx][nny]);
					progress--;
					Max = max(Max, day + 1);

					if (progress == 1) return Max;
				}
			}
			else if (find(g[hx][hy]) != find(g[nx][ny]))
			{
				merge(g[hx][hy], g[nx][ny]);
				progress--;
				Max = max(Max, day);

				if (progress == 1) return Max;
			}
		}
	}
}

int main()
{
	scanf("%d %d", &N, &M);
	for (i = 1; i <= M; i++)
	{
		int t1, t2;
		scanf("%d %d", &t1, &t2);
		g[t1 - 1][t2 - 1] = i;
		start.push_back(make_pair(t1 - 1, t2 - 1));
		q.push(make_pair(0, make_pair(t1 - 1, t2 - 1)));
		parent[i] = i;
	}

	progress = M;

	if (checkOne()) printf("0");
	else printf("%d", BFS());
	return 0;
}

djm03178 5년 전 5

이번 기회를 통해 여러 가지 알아가시면 좋겠습니다.

우선, 첫 번째 코드는 최적화를 시킬 경우 10초가 넘게 걸릴 코드가 아닙니다. 아마도 빌드 옵션을 디버그 모드로 하셨다고 추측되는데, 이 경우 최적화가 수행되지 않을 뿐 아니라 STL에서 내부적으로 수많은 디버깅 코드를 프로그램에 삽입하기 때문에 매우 매우 매우 느려집니다. 릴리즈 모드로 빌드하면 매우 빠르게 동작을 잘 하는 코드입니다.

그 다음, 두 번째 코드에는 치명적인 문제가 있습니다. checkOne 함수에서 BFS를 수행할 때, chk[hx][hy] = true;가 큐에서 뺀 다음에 수행된다는 것이 문제입니다. 이렇게 코드를 작성할 경우 어떤 칸이 둘 이상의 인접한 칸으로부터 동시에 큐에 삽입되더라도 막지를 못 합니다. 그러면 그 칸은 두 번 이상 방문이 되면서 인접한 칸들을 또 두 번 이상 큐에 넣고, 이게 수많은 칸들에 대해 연쇄적으로 수행되면 시간복잡도가 지수가 됩니다. 그래서 BFS를 할 때는 큐에 넣는 순간에 바로 chk를 설정해버리는 것이 좋습니다. 또는 큐에서 뺀 후 if (chk[hx][hy]) continue; 를 넣는 방법도 있지만 (다익스트라에서 주로 이렇게 합니다) 전자가 더 빠릅니다.

큰 입력을 여러 개 만들어보셨다고 하셨는데 단순히 N이 큰 것만 해보시고 정말 최악의 케이스를 넣어봤다고 생각하시면 안 됩니다. K가 큰 건 만들어보지 않으셨죠?

마지막으로, 질문을 올릴 때는 자기가 테스트한 내용이 중요한 게 아니라 코드에 대한 설명 (구현 로직, 함수의 역할 등)을 적는 게 중요합니다. 이렇게 긴 코드를 설명 한 줄 없이 올리면 읽고 싶은 사람이 있을까요?

#include <cstdio>
using namespace std;

int main()
{
	int n = 2000, k = 100000;
	printf("%d %d\n", n, k);
	for (int i = 0; i < 400; i++)
		for (int j = 0; j < 250; j++)
			printf("%d %d\n", i + 1, j + 1);
}

edenooo 5년 전 0

헉 이렇게 길고 부족한 질문에 답변해주셔서 정말 감사합니다.

디버그 모드와 릴리즈 모드의 차이점을 이제 알아가네요. 릴리즈 모드에서 실행해 보니 빠르게 잘 돌아갑니다 ㅎㅎ

그리고 BFS에서 원소가 중복으로 들어가게 코딩했다는 사실도 몰랐다니 아직 제 실력이 한참 모자란 것 같네요 ㅠㅠㅠㅠ

두 번째 코드는 checkOne() 부분을 정상 작동하게 고쳐 놓고, 말씀하신 대로 N과 K가 모두 큰 입력을 넣어 보았는데 BFS()에서 큐가 텅 빈 채로 무한루프를 도는 것을 보니 BFS()에서도 문제가 있는 것 같네요... 나중에 고쳐 보아야겠습니다.

다음에 질문을 올릴 일이 있다면 각 코드가 어떤 의미를 갖고 무슨 일을 하는지 간단하게라도 꼭 적어 놓도록 하겠습니다. 새벽에 정신없이 올리다 보니 질문을 잘 못 쓴 것 같네요.

다시 한 번 감사드립니다!

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

문제

문제

출처

ICPC

14868번 문명) 맞은 코드보다 더 빠른 코드가 왜 시간초과날까요?

edenooo 5년 전 0

djm03178 5년 전 5

edenooo 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말