[BOJ/백준] 14502번 - 연구소 C++ 문제 풀이(시간 초과 포함)

문제 링크 : https://www.acmicpc.net/problem/14502

14502번: 연구소

 

 

[문제 요약]

0 : 빈 칸 / 1 : 벽 / 2 : 바이러스

 

바이러스는 상하좌우 인접한 빈 칸으로 모두 펴져나간다.

이때, 우리는 벽을 3개 세울 수 있고, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다.

안전 영역 크기의 최댓값을 구하시오.

 

 

[문제 접근]

1. 바이러스가 상하좌우로 퍼진다. → BFS

2. 벽을 3개 세울 수 있다. → 조합 : 모든 빈칸(0) 중 3개를 선택해 벽(1)을 세운 뒤, 모든 경우의 안전 영역을 구한다. 

3. 중요한 건, 원본 그래프를 복사하여 사용해야 한다.

 

 

[조합 코드를 짜는 여러가지 방법]

다른 분들의 코드를 보며 느낀 점은 벽을 세우는 여러 가지 방법이 있다는 것이다.

 

    1. 맵 전체를 돌며 빈칸이 나올 시, 3개씩 선택하는 조합 함수로 이동.

    2. 맵 전체를 돌며 빈칸이 나올 시, 해당 빈칸은 벽으로 바꾼 뒤, 2개씩 선택하는 조합 함수로 이동.

    3. 입력 받을 시, 모든 빈칸을 1차원 배열로 받은 뒤, 해당 배열을 조합하는 방법.

 

 

 

방법 1. 맵 전체를 돌며 빈칸이 나올 시, 3개씩 선택하는 조합 함수로 이동.

/* a[i][j] : 입력 받은 맵, copy() : 원본 그래프를 복사하는 함수, wall() : 조합을 진행하는 함수
*/

// 빈 칸이 나올 시, 1. 원본 그래프 복사, 2. 조합 함수(3개씩 뽑는) 이동
for(int i=0; i<n; i++) {
	for(int j=0; j<m; j++) {
		if(a[i][j]==0) {
			copy(tmp, a);
			wall(0);
		}
	}
}

// 조합 함수
void wall(int cur) {
	if(cur==3) {
		bfs();
		return;
	}
	
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(tmp[i][j]==0) {
				tmp[i][j] = 1;
				wall(cur+1);
				tmp[i][j] = 0;
			}
		}
	}
}

 

 

방법 2. 맵 전체를 돌며 빈칸이 나올 시, 해당 빈칸은 벽으로 바꾼 뒤, 2개씩 선택하는 조합 함수로 이동.

for(int i=0; i<n; i++) {
	for(int j=0; j<m; j++) {
		if(a[i][j]==0) {
			memset(vis, 0, sizeof(vis));
			copy(tmp, a);
			tmp[i][j]=1;
			wall(1);
			tmp[i][j]=0;
		}
	}
}

void wall(int cur) {
	if(cur==3) {
		bfs();
		return;
	}
	
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(tmp[i][j]==0) {
				tmp[i][j] = 1;
				wall(cur+1);
				tmp[i][j] = 0;
			}
		}
	}
}

 

 

방법 3. 입력 받을 시, 모든 빈칸을 1차원 배열로 받은 뒤, 해당 배열을 조합 하는 방법.

cin >> n >> m;
for(int i=0; i<n; i++) {
	for(int j=0; j<m; j++) {
		cin >> a[i][j];
		if(a[i][j]==0) {
			space.push_back({i, j});
		}
    }
}


wall(0, 0);

void wall(int cur, int idx) {

	if(cur==3) {
		copy(tmp, a);
		int cnt=0;
		for(int i=0; i<space.size(); i++) {
			if(cnt==3) break;
			if(vis[i]) {
				int x = space[i].first;
				int y = space[i].second;
				tmp[x][y] = 1;
				cnt++;
			}
		}
		bfs();
		return;
	}
	
	for(int i=idx; i<space.size(); i++) {
		if(vis[i]) continue;
		vis[i] = true;
		wall(cur+1, i);
		vis[i] = false;
	}
}

 

 

결론부터 말하자면, 방법1은 시간 초과, 방법 2, 3은 통과가 된다.

 

방법 1. 맵 전체를 돌며 빈칸이 나올 시, 3개씩 선택하는 조합 함수로 이동.

 

방법 2. 맵 전체를 돌며 빈칸이 나올 시, 해당 빈칸은 벽으로 바꾼 뒤, 2개씩 선택하는 조합 함수로 이동.

 

방법 3. 입력 받을 시, 모든 빈칸을 1차원 배열로 받은 뒤, 해당 배열을 조합하는 방법.

 

 

[CODE]

<방법 2.>를 통해 짠 코드

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

const int mxN=8, dx[4]={1, -1, 0, 0}, dy[4]={0, 0, 1, -1};
int n, m, a[mxN][mxN];
int tmp[mxN][mxN];
int ans=0;
bool vis[mxN][mxN];

void copy(int tmp[mxN][mxN], int a[mxN][mxN]) {
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			tmp[i][j] = a[i][j];
		}
	}
}

void bfs() {
	int after[8][8];
	copy(after, tmp);
	
	queue<pair<int, int>> q;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(after[i][j]==2) {
				q.push({i, j});
			}
		}
	}
	
	while(q.size()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		for(int k=0; k<4; k++) {
			int nx = x+dx[k];
			int ny = y+dy[k];
			
			if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
			if(after[nx][ny]==0) {
				after[nx][ny] = 2;
				q.push({nx, ny});
			}
		}
	}
	
	int cnt=0;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(after[i][j]==0) {
				cnt++;
			} 
		}
	}
	ans = max(ans, cnt);
}

void wall(int cur) {
	if(cur==3) {
		bfs();
		return;
	}
	
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(tmp[i][j]==0) {
				tmp[i][j] = 1;
				wall(cur+1);
				tmp[i][j] = 0;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
 	cout.tie(0);
	
	cin >> n >> m;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			cin >> a[i][j];
		}
	}
	
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(a[i][j]==0) {
				memset(vis, 0, sizeof(vis));
				copy(tmp, a);
				tmp[i][j]=1;
				wall(1);
				tmp[i][j]=0;
			}
		}
	}
	
	cout << ans;
}

 

<방법3.>을 통해 짠 코드

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

const int mxN=8, dx[4]={1, -1, 0, 0}, dy[4]={0, 0, 1, -1};
int n, m, a[mxN][mxN];
int tmp[mxN][mxN];
int ans=0;
bool vis[mxN * mxN];
vector<pair<int, int>> space;

void copy(int tmp[mxN][mxN], int a[mxN][mxN]) {
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			tmp[i][j] = a[i][j];
		}
	}
}

void bfs() {
	
	queue<pair<int, int>> q;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(tmp[i][j]==2) {
				q.push({i, j});
			}
		}
	}
	
	while(q.size()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		for(int k=0; k<4; k++) {
			int nx = x+dx[k];
			int ny = y+dy[k];
			
			if(nx<0 || nx>=n || ny<0 || ny>=m) continue;
			if(tmp[nx][ny]==0) {
				tmp[nx][ny] = 2;
				q.push({nx, ny});
			}
		}
	}
	
	int cnt=0;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			if(tmp[i][j]==0) {
				cnt++;
			} 
		}
	}
	ans = max(ans, cnt);
}

void wall(int cur, int idx) {

	if(cur==3) {
		copy(tmp, a);
		int cnt=0;
		for(int i=0; i<space.size(); i++) {
			if(cnt==3) break;
			if(vis[i]) {
				int x = space[i].first;
				int y = space[i].second;
				tmp[x][y] = 1;
				cnt++;
			}
		}
		bfs();
		return;
	}
	
	for(int i=idx; i<space.size(); i++) {
		if(vis[i]) continue;
		vis[i] = true;
		wall(cur+1, i);
		vis[i] = false;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
 	cout.tie(0);
	
	cin >> n >> m;
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			cin >> a[i][j];
			if(a[i][j]==0) {
				space.push_back({i, j});
			}
		}
	}

	wall(0, 0);
	
	cout << ans;
}

 

 

해당 문제를 통해 'BFS+조합'을 구성하는 법과 '그래프 복사'에 대해 배울 수 있었습니다.

또, 구현 시 여러 함수를 통해 나누어 코드를 작성하는 방법을 익힐 수 있었습니다.