[코딩테스트 스터디/C++] 백준 14502번 연구소

1.문제 링크

https://www.acmicpc.net/problem/14502

2. 풀이 전 계획과 생각

• BFS나 DFS 이용해서 풀기

• 저번에 푼 백준 15686번 치킨배달의 비트를 이용해 조합 구하기

3. 풀이

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int N,M;

int lab[8][8]; // 연구소   
int tmp[8][8]; // 연구소 복사  

bool check[8][8]; 

vector<pair<int,int> > zero; // lab좌표 중 0인 좌표 저장  

// 연구소 복사  
void copyLab(){
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++) tmp[i][j]=lab[i][j];
	}
}

// 바이러스 퍼트리기  
void dfs(int x, int y) {
    // 주어진 범위를 벗어나는 경우에는 즉시 종료  
    if (x <= -1 || x >=N || y <= -1 || y >= M)  return;
    // 벽을 만나면 종료  
    if(tmp[x][y]==1) {
    	check[x][y]=true;
    	return;
	}
	 
    if(check[x][y]==true) return; // 이미 체크한 위치라면 종료 
    
    check[x][y]=true;
    
    // 벽이 아니면서 바이러스가 퍼지지 않은 구역이라면  
	if(tmp[x][y] == 0) {
        tmp[x][y] = 2; // 바이러스 퍼트리기  
    }
    
    // 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
    dfs(x - 1, y);
    dfs(x, y - 1);
    dfs(x + 1, y);
    dfs(x, y + 1);
}

// 안전구역 count  
int countSafeZone(){
	int cnt=0;
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
	    	if(tmp[i][j]==0) cnt++;
		}
	}
	return cnt;
}

int main(){
	// 입출력 빨라지게 해줌. 
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	// 입력  
	cin>>N>>M;
	
	// 입력  
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++) cin>>lab[i][j];
	}
	
	// '0' 좌표 zero 벡터에 저장  
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			if(lab[i][j]==0) zero.push_back({i,j});	
		}
	}
	
	// 조합을 위한 코드  
	vector<int> ind;
	int k=3;
	for(int i=0; i<k; i++){
		ind.push_back(1);
	}
	for(int i=0; i<zero.size()-k; i++){
		ind.push_back(0);
	}
	sort(ind.begin(), ind.end());
	
	
	int ans=0;	
	do{
		copyLab();
		
		for(int i=0;i<N;i++){
			for(int j=0;j<M;j++) check[i][j]=false;
		}
		
		// 조합  
		for(int i=0; i<ind.size(); i++){
			if(ind[i] == 1){
				tmp[zero[i].first][zero[i].second]=1;
			}
		}
		
		for(int i=0;i<N;i++){
			for(int j=0;j<M;j++){
				if(tmp[i][j]==2 && check[i][j]==false) dfs(i,j);
			}
		}
		
		ans = max(ans, countSafeZone());
		
	}while(next_permutation(ind.begin(), ind.end()));		
	
	// 정답 출력  
	cout<<ans;
}

1. 원소 연구소 상태를 임시 배열에 복사.
2. 벽 3개를 세우기 위해 조합을 이용. 모든 경우에 대해서 구현함. 벽 3개를 세움.
3. dfs를 이용해 바이러스를 퍼트림.
4. 안전구역 즉 0의 개수를 센다.
5. 가장 큰 안전구역 수가 정답.

4. 풀이하면서 고민했던 점

• 조합을 구할 때 비트연산을 이용했는데 시간초과로 실패했다.

int ans=0;
	for(long long set=0; set<pow(2,zero.size()); set++){
		if(count_OneBits(set)==3){
			
			copyLab();
            ...
            ...
    }

위 코드처럼 비트를 이용해 조합을 구현하려 했다. 하지만 시간초과 때문에 실패했다.

5. 문제를 풀고 알게된 개념 및 소감

• 조합을 구하는 방법에 대해 알게됨