글 읽기 - 쓸데 없는 코드를 지우면 속도가 느려집니다.

njh7799 5년 전 0

문제를 풀 때에 처음 접근 방법을 버리고 다른 접근 방법으로 풀었습니다. 첫 접근 때 썼던 코드는 일단은 두고 나중에 지우려고 했는데, 이 부분을 지우고 실행하면 지우지 않았을 때 보다 속도가 느려집니다. (지우지 않았을 때: 350 정도, 지웠을 때 500정도)

지운 부분은 제가 문제를 해결하는데 사용한 알고리즘에 아무런 영향을 끼지치 않습니다.

//너무 조잡하게 풀었음
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

struct Point {
	int x;
	int y;
	bool operator==(const Point &rhs) const {
		return this->x == rhs.x && this->y == rhs.y;
	}
};

int maxi = -1 << 20;
int parent[401];// union-find를 위한 부모 배열
Point position[401];// 검은 돌의 인덱스를 넣었을 때 좌표를 찍어줌
Point blank[400];
int idx = 1;//검은 돌의 인덱스
int bkidx = 0;
int n, m;
int a[20][20];
int setting[20][20];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0 ,-1 };
vector<int> v;




////////////필요 없는 부분 1//////////////

int findset(int a) {
	if (a == parent[a]) return a;
	else return parent[a] = findset(parent[a]);
}

void unionset(int a, int b) {
	parent[b] = a;
}

bool issameset(int a, int b) {
	return findset(a) == findset(b);
}

///////////////////////////////////////




// 흰 돌을 두개 배치 하였을 때 죽일 수 있는 검은돌의 최대 개수를 세어주는 함수
void countblack() {
	int total = 0;
	bool ck[20][20] = { false, };
	for (int i = 1; i < idx; i++) {
		if (!ck[position[i].x][position[i].y]) {
			int cnt = 1;
			bool flag = false;
			queue<Point> q;
			q.push(position[i]);
			while (!q.empty()) {
				Point crr = q.front();
				q.pop();
				ck[crr.x][crr.y] = true;
				for (int dir = 0; dir < 4; dir++) {
					int nx = crr.x + dx[dir];
					int ny = crr.y + dy[dir];
					if (nx >= 0 && nx < n && ny >= 0 && ny < m && !ck[nx][ny]) {
						if (a[nx][ny] == 2) {
							q.push({ nx, ny });
							ck[nx][ny] = true;
							cnt++;
						}
						if (a[nx][ny] == 0) flag = true;
					}
				}
			}
			if (flag) cnt = 0;
			total += cnt;
		}
	}
	if (total > maxi) maxi = total;
}


int main() {
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &a[i][j]);
			if (a[i][j] == 2) {
				position[idx] = { i,j };//특정 인덱스의 검은돌 실제 위치 저장
				setting[i][j] = idx++;
			}

		}
	}






	/////////////////////////////필요 없는 부분 2///////////////////////////////////////////////////


	for (int i = 1; i < idx; i++) parent[i] = i;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (setting[i][j]) {
				for (int dir = 0; dir < 2; dir++) {
					int nx = i + dx[dir];
					int ny = j + dy[dir];
					if (nx >= 0 && nx < n && ny >= 0 && ny < m && setting[nx][ny]) {
						unionset(setting[i][j], setting[nx][ny]);
					}
				}
			}
		}
	}
	for (int i = 1; i < idx; i++) findset(i);
	bool checkvector[401] = { false, };
	for (int i = 1; i < idx; i++) {
		if (!checkvector[parent[i]]) {
			v.push_back(parent[i]);
			checkvector[parent[i]] = true;
		}
	}

	//////////////////////////////////////////////////////////////////////////////////////////






	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (a[i][j] == 0) {
				blank[bkidx++] = { i,j };
			}
		}
	}



	//흰돌을 배치 + 잡을 수 있는 검은 돌 세어주기
	for (int first = 0; first < bkidx - 1; first++) {
		for (int second = first + 1; second < bkidx; second++) {
			a[blank[first].x][blank[first].y] = 1;
			a[blank[second].x][blank[second].y] = 1;

			countblack();

			a[blank[first].x][blank[first].y] = 0;
			a[blank[second].x][blank[second].y] = 0;
		}
	}


	printf("%d", maxi);
}

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

문제

문제

출처

ICPC

쓸데 없는 코드를 지우면 속도가 느려집니다.

njh7799 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말