백준 - 마법사 상어와 파이어스톰 (20058번)

백준 - 마법사 상어와 파이어스톰 (20058번)

vector를 쓰면 시간초과에 턱도없이 걸린다 (미리 할당해서 쓰는건 괜찮을지 모르겠는데, 그럴거면 그냥 배열 쓰는거랑 다를바가 없다)

// 시간초과에 계속 걸리는 코드
void melting(int iter)
{
	vector<pos> minus;
	for (int row = 0; row < n; row++) {
		for (int col = 0; col < n; col++) {
			if (map[row][col] == 0)
				continue;
			int ice_cnt = 0;
			for (int i = 0; i < 4; i++) {
				int nrow = row + rowDir[i];
				int ncol = col + colDir[i];
				if (!is_safe(nrow, ncol))
					continue;
				if (map[nrow][ncol] > 0)
					ice_cnt++;
			}
			if (ice_cnt < 3) 
				minus.push_back({ row, col });
		}
	}
	for (int i = 0; i < minus.size(); i++) {
		pos c = minus[i];
		map[c.row][c.col] = map[c.row][c.col] > 0 ? map[c.row][c.col] - 1 : 0;
	}
}

// 통과한 코드
int tmpMap[128][128];
void melting(int iter)
{
	for (int row = 0; row < n; row++) {
		for (int col = 0; col < n; col++) {
			if (map[row][col] == 0)
				continue;
			int ice_cnt = 0;
			for (int i = 0; i < 4; i++) {
				int nrow = row + rowDir[i];
				int ncol = col + colDir[i];
				if (!is_safe(nrow, ncol))
					continue;
				if (map[nrow][ncol] > 0)
					ice_cnt++;
			}
			if (ice_cnt < 3) 
				tmpMap[row][col] = iter;
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (tmpMap[i][j] == iter)
				map[i][j] = map[i][j] > 0 ? map[i][j] - 1 : 0;
		}
	}
}

또한 시계방향으로 rotate하는 로직을 좀 더 개선하면 시간을 좀 더 줄일 수 있을 것 같다.
현재는 배열을 그대로 복사한 뒤 다시 원래 것에 복사해주느라 배열 순회를 2번하고 있다.

총 코드는 아래와 같다.

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

using namespace std;

int n, q;
int map[128][128];
int magic[1000];

int rowDir[4] = { -1, 0, 1, 0 };
int colDir[4] = { 0, 1, 0, -1 };
typedef struct __pos {
	int row;
	int col;
	int value;
}pos;
void print_map(const char* s)
{
	printf("%s\n", s);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			printf("%d\t", map[i][j]);
		}
		printf("\n");
	}
}
const inline bool is_safe(int row, int col)
{
	if (row < 0 || row > n - 1 || col < 0 || col > n - 1)
		return false;
	return true;
}

pos tmpV1[128][128];
void rotate_body(int row, int col, int skip)
{
	int row_end = row + skip;
	int col_end = col + skip;
	for (int i = row; i < row_end; i++) 
		for (int j = col; j < col_end; j++) 
			tmpV1[i - row][j - col] = { i, j, map[i][j] };
		
	for (int i = 0; i < skip; i++) 
		for (int j = 0; j < skip; j++) 
			map[tmpV1[j][skip - i - 1].row][tmpV1[j][skip - i - 1].col] = tmpV1[i][j].value;
}

void rotate(int skip)
{
	for (int row = 0; row < n; row += skip)
		for (int col = 0; col < n; col += skip)
			rotate_body(row, col, skip);
}

int tmpMap[128][128];
void melting(int iter)
{
	for (int row = 0; row < n; row++) {
		for (int col = 0; col < n; col++) {
			if (map[row][col] == 0)
				continue;
			int ice_cnt = 0;
			for (int i = 0; i < 4; i++) {
				int nrow = row + rowDir[i];
				int ncol = col + colDir[i];
				if (!is_safe(nrow, ncol))
					continue;
				if (map[nrow][ncol] > 0)
					ice_cnt++;
			}
			if (ice_cnt < 3) {
				tmpMap[row][col] = iter;
			}
		}
	}

	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			if (tmpMap[i][j] == iter)
				map[i][j] = map[i][j] > 0 ? map[i][j] - 1 : 0;
		
	
}
void solve(int iter, int level)
{
	int skip = 1 << level;
	rotate(skip);
	melting(iter);
}

int visit[128][128];
int answer = 0;
void bfs(int row, int col)
{

	queue<pos> q;
	q.push({ row, col });
	int cnt = 0;
	while (1) {
		if (q.empty())
			break;

		pos cur = q.front(); q.pop();
		for (int i = 0; i < 4; i++) {
			pos n;
			n.row = cur.row + rowDir[i];
			n.col = cur.col + colDir[i];
			if (!is_safe(n.row, n.col))
				continue;
			if (visit[n.row][n.col])
				continue;
			if (map[n.row][n.col] == 0)
				continue;
			visit[n.row][n.col] = 1;
			q.push(n);
			cnt++;
		}
	}
	answer = max(cnt, answer);
}

int get_continuous()
{
	int answer = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 0)
				continue;
			if (visit[i][j] == 0) 
				bfs(i, j);
		}
	}	

	return answer;
}
int get_total()
{
	int total = 0;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			total += map[i][j];

	return total;
}
int main(void)
{
	cin >> n >> q;
	n = (1 << n);
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			cin >> map[i][j];

	for (int i = 0; i < q; i++) 
		cin >> magic[i];
	
	for (int iter = 0; iter < q; iter++) {
		int level = magic[iter];
		solve(iter + 1, level);
	}

	int total = get_total();
	if (total == 0)
		answer = 0;
	else
		get_continuous();
	cout << total << "\n";
	cout << answer << "\n";

	return 0;
}