글 읽기 - 시간을 많이 잡아먹는 부분이 어디일까요?

pkc4913 4년 전 0

일단 최악의 시간복잡도를 계산하기론

64P3 * 8*8 = 16000000정도라서

무리는 없겠다고 생각했는데 첫번째 케이스는 1초정도 걸리고 마지막 케이스는 3분 기다려도 답이 안나옵니다..

어디를 고쳐야 될까요?

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> P;
int borad[8][8];
bool pvisited[8][8], visited[8][8];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int N, M;
vector<P> v;
int ans;
void bfs(int r, int c) {
	visited[r][c] = true;
	queue<P> q;
	q.push({ r,c });
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
			if (visited[nx][ny]) continue;
			if (borad[nx][ny] != 0) continue;
			q.push({ nx,ny });
			visited[nx][ny] = true;
		}
	}
}
void pm(int cnt) {
	if (cnt == 3) {
		for (int i = 0; i < v.size(); i++) {
			int nx = v[i].first;
			int ny = v[i].second;
			borad[nx][ny] = true;
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (borad[i][j] == 2) bfs(i, j);
			}
		}
		int tmp = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (!visited[i][j] && !borad[i][j]) tmp++;
				//침투되지 않았고 빈공간이면
			}
		}
		ans = max(tmp, ans);
		memset(visited, 0, sizeof(visited));
		for (int i = 0; i < v.size(); i++) {
			int nx = v[i].first;
			int ny = v[i].second;
			borad[nx][ny] = false;	
		}
		return;
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (pvisited[i][j]) continue;
			if (borad[i][j] != 0) continue;
			pvisited[i][j] = true;
			v.push_back({ i,j });
			pm(cnt + 1);
			pvisited[i][j] = false;
			v.pop_back();
		}
	}

}
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			scanf("%d", &borad[i][j]);
	pm(0);
	printf("%d", ans);
}

djm03178 4년 전 1

빌드를 디버깅 모드로 하는 것을 고치셔야 합니다. 릴리즈 모드로 빌드해 보세요.

이 코드로 그대로 제출해도 348ms에 잘 통과됩니다.

pkc4913 4년 전 0

감사합니다

64 릴리즈 모드로 하니 잘 됩니다

그리고 생각해보니 순열로 구현할 필요가 없었네요

조합으로 하면 더 빨랐을텐데요..

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

문제

문제

출처

ICPC

시간을 많이 잡아먹는 부분이 어디일까요?

pkc4913 4년 전 0

djm03178 4년 전 1

pkc4913 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말