글 읽기 - 다른 정답코드에 비해서 실행속도가 느린이유

swj0324 2년 전 0

다른 사람들 정답코드는 30~40ms 가 나오는데 반해

제 코드는 350ms 가 나오는데

어디가 비효율 적일까요..?

코드 지적 부탁드립니다.

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

using namespace std;

int n, m; // 행, 열

int cal(vector<vector<int>>& lab, int blank){
	vector<vector<vector<pair<int, int>>>> adj (n, vector<vector<pair<int, int>>>(m));
	
	queue<pair<int, int>> q;
	vector<vector<bool>> visited(n, vector<bool>(m, false));
	
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(lab[i][j]!=1){
				if(lab[i][j]==2){
					q.push(make_pair(i, j));
					visited[i][j] = true;
				}
				if(i>=1&&lab[i-1][j]!=1){
					adj[i][j].push_back(make_pair(i-1, j));
				}
				if(i<=n-2&&lab[i+1][j]!=1){
					adj[i][j].push_back(make_pair(i+1, j));
				}
				if(j>=1&&lab[i][j-1]!=1){
					adj[i][j].push_back(make_pair(i, j-1));
				}
				if(j<=m-2&&lab[i][j+1]!=1){
					adj[i][j].push_back(make_pair(i, j+1));
				}
			}
		}
	}
	
	while(!q.empty()){
		int row = q.front().first;
		int col = q.front().second;
		q.pop();
		visited[row][col] = true;
		
		for(int i=0; i<adj[row][col].size(); i++){
			int next_row = adj[row][col][i].first;
			int next_col = adj[row][col][i].second;
			if(!visited[next_row][next_col]){
				blank--;
				visited[next_row][next_col] = true;
				q.push(make_pair(next_row, next_col));
			}
		}
	}
	
	return blank;
}



int main(){
	std::ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);
	
	cin >> n >> m;
	
	vector<vector<int>> lab(n, vector<int>(m, 0));
	
	int blank = n*m;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			cin >> lab[i][j];
			if(lab[i][j]){
				blank--;
			}
		}
	}
	
	int ans = 0;
	
	for(int i=0; i<n*m; i++){
		for(int j=i+1; j<n*m; j++){
			for(int k=j+1; k<n*m; k++){
				if(lab[i/m][i%m]==0&&lab[j/m][j%m]==0&&lab[k/m][k%m]==0){
					lab[i/m][i%m] = 1; lab[j/m][j%m] = 1; lab[k/m][k%m] = 1;
					int safe_sector = cal(lab, blank-3);
					ans = safe_sector > ans ? safe_sector : ans;
					lab[i/m][i%m] = 0; lab[j/m][j%m] = 0; lab[k/m][k%m] = 0;
				}
			}
		}
	}
	
	cout << ans << "\n";
}

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

문제

문제

출처

ICPC

다른 정답코드에 비해서 실행속도가 느린이유

swj0324 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말