글 읽기 - 시간 초과 질문드립니다

skh2080 3년 전 0

얼음이 녹는 걸 체크할 때 주위 4방향을 둘러보느라 대략 16400번 필요한 걸로 알고있습니다.

마법이 최대 1000번 사용되기 때문에 1640만번 이상의 계산이라는 결과가 나오는데 시간 제한을 통과 못하네요...

여기서 어떻게 시간을 더 줄여야 될까요?

#include <iostream>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;
int N;
int n;
int q;
int ret;
int cur;
int a[2][64][64];
int status[64][64];
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, -1, 0, 1 };

//void dfs(int len, int sy, int sx, int level) {
//	int m = 1 << (level - 1);
//	if (len == 2 * m) {
//		for (int i = sy; i < sy + m; ++i) {
//
//
//
//			for (int j = sx; j < sx + m; ++j) {
//				a[1-cur][i][j + m] = a[cur][i][j];
//			}
//
//			for (int j = sx + m; j < sx + 2 * m; ++j) {
//				a[1-cur][i + m][j] = a[cur][i][j];
//			}
//		}
//
//		for (int i = sy + m; i < sy + 2 * m; ++i) {
//			for (int j = sx; j < sx + m; ++j) {
//				a[1-cur][i - m][j] = a[cur][i][j];
//			}
//
//			for (int j = sx + m; j < sx + 2 * m; ++j) {
//				a[1-cur][i][j - m] = a[cur][i][j];
//			}
//		}
//		return;
//	}
//	//네가지로 나누기.
//	for (int i = 0; i * 2 < len; ++i) {
//		dfs(len / 2, sy, sx, level);
//		dfs(len / 2, sy, sx + len / 2, level);
//		dfs(len / 2, sy + len / 2, sx, level);
//		dfs(len / 2, sy + len / 2, sx + len / 2, level);
//	}
//}

void dfs(int len, int sy, int sx, int level) {
	int m = 1 << (level - 1);
	if (len == 2 * m) {
		for (int i = sy; i < sy + 2 * m; ++i) {
			for (int j = sx; j < sx + 2 * m; ++j) {
				a[1 - cur][i][j] = a[cur][sx + 2 * m - 1 - j + sy][sx + i - sy];
			}
		}
		return;
	}
	//네가지로 나누기.
	for (int i = 0; i * 2 < len; ++i) {
		dfs(len / 2, sy, sx, level);
		dfs(len / 2, sy, sx + len / 2, level);
		dfs(len / 2, sy + len / 2, sx, level);
		dfs(len / 2, sy + len / 2, sx + len / 2, level);
	}
}

void bfs(int sy, int sx, int status[][64], int index) {
	int visited[64][64] = { 0, };
	int sum = 0;
	queue<pair<int, int> > q;

	visited[sy][sx] = 1;
	q.push({ sy, sx });
	while (!q.empty()) {
		
		int y, x;
		tie(y, x) = q.front(); q.pop();
		status[y][x] = index;
		sum++;
		for (int dir = 0; dir < 4; ++dir) {
			int ny = y + dy[dir];
			int nx = x + dx[dir];
			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if (visited[ny][nx] == 0 && a[cur][ny][nx] > 0) {
				visited[ny][nx] = 1;
				q.push({ ny, nx });
			}
		}
	}

	if (sum > ret) ret = sum;
}

void melt() { //얼음녹기. 순차적으로 진행되기 때문에 map이 두개가 필요하다. 4*2^2N = 16400
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (a[cur][i][j] == 0) {
				a[1 - cur][i][j] = 0;
				continue;
			}
			int cnt = 0;
			for (int dir = 0; dir < 4; ++dir) {
				int ny = i + dy[dir];
				int nx = j + dx[dir];
				if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
				if (a[cur][ny][nx] > 0) cnt++;
			}
			if (cnt >= 3) a[1 - cur][i][j] = a[cur][i][j];
			else a[1 - cur][i][j] = a[cur][i][j] - 1;
		}
	}
	cur = 1 - cur;
}

int main() {
	int level;
	int sum = 0;
	int status_idx = 0;
	vector<int> order;
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> q;
	N = 1 << n;
	for (int i = 0; i < (1<<n); ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> a[cur][i][j];
		}
	}
	for (int k = 0; k < q; ++k) {
		cin >> level;
		order.push_back(level);
	}
	for (auto level : order) { // 1000
		if (level != 0) { // 2^2N = 4096
			dfs(1 << n, 0, 0, level);
			cur = 1 - cur;
		}
		melt();
	}
	// 남은 거 더하기. 2^2N = 4096
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (a[cur][i][j] > 0) sum += a[cur][i][j];
		}
	}
	// bfs로 제일 큰 덩어리 찾기. 2^2N = 4096
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (status[i][j] == 0 && a[cur][i][j] > 0) {
				status_idx++;
				bfs(i, j, status, status_idx);
			}
		}
	}
	//대략 2천만번
	cout << sum << "\n";
	cout << ret << "\n";
	return 0;
}

wjdwjd95 3년 전 0

저도 녹이는 부분 구현은 똑같은데 통과했어요,, 녹이는 부분이 문제는 아닌 것 같아요
저는 녹이면서 남은거 갯수를 세아려줘서 남은거 더하기 하는 부분이 없는 차이 말고는 다른게 없는 것 같네요,,

skh2080 3년 전 0

으아으아으아으아...

skh2080 3년 전 0

이 뭔 씹... dfs코드 복붙했다가 피본거네요

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

문제

문제

출처

ICPC

시간 초과 질문드립니다

skh2080 3년 전 0

wjdwjd95 3년 전 0

skh2080 3년 전 0

skh2080 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말