글 읽기 - 복사하는 과정에서 너무 많은 시간을 뺏기는 것 같습니다

luckyquit 4년 전 0

패스한 코드입니다.

코드를 보시면 bfs() 함수에서 맵과 바이러스 좌표를 담은 벡터를 계속해서 복사하는 식입니다.

맵의 크기는 8*8이라서 크지는 않지만 dfs로 3개의 벽을 세우는 모든 경우를 전부 복사한 후에 비교하기 때문에

꽤 많은 시간을 뺏긴다고 생각합니다.

이 부분을 개선시킬 방법이 있을까요? 힌트라도 좋습니다.

그 외에 개선점도 지적해주시면 감사하겠습니다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int, int> pi;

const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };

int n, m, map[8][8];
bool chk[8][8];

vector<pi> virus;

int bfs()
{
	bool visited[8][8] = { false, };
	queue<pi> q;

	int copy[8][8];
	for (int y = 0; y < n; y++)
		for (int x = 0; x < m; x++)
			copy[y][x] = map[y][x];

	for (auto it = virus.begin(); it != virus.end(); ++it)
		q.push(*it);

	while (!q.empty()) {
		int sz = q.size();
		
		while (sz--) {
			pi cur = q.front();
			q.pop();

			visited[cur.first][cur.second] = true;

			for (int dir = 0; dir < 4; dir++) {
				int ny = cur.first + dy[dir];
				int nx = cur.second + dx[dir];

				if (ny < 0 || nx < 0 || ny >= n || nx >= m)
					continue;
				if (copy[ny][nx] == 0 && !visited[ny][nx]) {
					copy[ny][nx] = 2;
					q.push({ ny,nx });
				}
			}
		}
	}

	int ret = 0;
	for (int y = 0; y < n; y++)
		for (int x = 0; x < m; x++)
			if (copy[y][x] == 0)
				ret++;

	return ret;
}

int ans = -987654321;
void dfs(int cnt, int cy, int cx)
{
	if (cnt == 3) {
		int cmp = bfs();
		if (ans < cmp) ans = cmp;
		return;
	}

	for (int y = 0; y < n; y++)
		for (int x = 0; x < m; x++) {
			if (chk[y][x] || map[y][x] != 0)
				continue;

			chk[y][x] = true; map[y][x] = 1;
			dfs(cnt + 1, y, x);
			chk[y][x] = false; map[y][x] = 0;
		}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	
	cin >> n >> m;
	for (int y = 0; y < n; y++)
		for (int x = 0; x < m; x++) {
			cin >> map[y][x];
			chk[y][x] = false;

			if (map[y][x] == 2)
				virus.push_back({ y,x });
		}

	dfs(0, 0, 0);

	cout << ans;
}

luckyquit 4년 전 0

na982라는 유튜버의 영상을 참고 했을 때

맵의 크기가 10을 넘지 않으므로

vector<int> virus;

virus.push(y*10, x);

queue<int> q;

for(auto it = virus.begin(); it != virus.end(); ++it)

q.push(*it);

int cur = q.front();

q.pop();

int cy = cur/10;

int cx = cur%10;

이런식의 저장 방식도 꽤 괜찮은 거 같군요.

bupjae 4년 전 0

23 ~ 25 번째 줄은 memcpy 로 대체할 수 있을 것 같습니다.

30 번째 줄 부터 시작하는 반복문은 굳이 2중 반복문을 쓸 필요는 없어 보입니다.

이렇게 하면 조금이나마 효율적인 코드가 될 것 같지만, 시간복잡도는 달라지지 않으므로 실제 시간 이득은 별로 없을 것 같습니다.

bupjae 4년 전 0

x, y 좌표를 하나의 수로 저장하는 방법은 메모리 절약 면에서는 이득일 수 있지만 좌표를 합치고 나누는 연산에 시간을 더 많이 소요할 수 있습니다.

또한, 이것 역시 시간/공간 복잡도는 달라지지 않으므로 겉으로 드러날 만한 차이는 별로 없을 것 같습니다.

seico75 4년 전 0

벽을 충분히 큰 수 0x7fffffff 정도로 치환을 해둔 다음에..

BFS에서 각 칸이 2보다 작으면 빈칸으로 보고 2로 채우면서 퍼지는 공간을 재보고..

다음에는 3보다 작으면 빈칸으로 보고 3으로 채우면서...

...

x보다 작으면 빈칸으로 보고 x로 채우면서.. (x는 2부터 시작해서..)

이문제에서는 8x8 이 최대이므로 64*63*62의 경우의 수가 생겨서 x가 그만큼 늘 수 있겠지만 0x7fffffff 보다는 작으니 통할 것 같습니다.

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

문제

문제

출처

ICPC

복사하는 과정에서 너무 많은 시간을 뺏기는 것 같습니다

luckyquit 4년 전 0

luckyquit 4년 전 0

bupjae 4년 전 0

bupjae 4년 전 0

seico75 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말