[백준 14502번] 연구소 - C++ (삼성 SW역량테스트 기출)

BFS로 풀었고, 난이도는 그렇게 어렵지 않지만 문제 풀이 절차를 잘 파악해야 하는 문제라고 생각합니다.

 

 문제출처

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

14502번: 연구소

 

저는 함수를 사용해서 복잡한 풀이 절차를 나눴습니다.

 

전체적인 풀이 방식

 

처음 입력 받은 배열(origin)을 다른 배열(map)에 복사하고, map에서 매번 다른 위치에 3개의 벽을 설치한 뒤 바이러스를 퍼뜨려 보면서 안전지대 크기를 비교합니다.

 

1. 맨 처음 배열을 origin에 저장하고 0인 좌표, 즉 벽을 설치할 수 있는 위치들을 zeros벡터에 저장한다. 벽설치를 임시로 해보기 위해 origin을 map에 복사한다.

 

2. zeros 벡터에 대해 next_permutation을 돌면서 조합으로 3개 위치를 뽑고, map에서의 이 위치에 벽을 세운다.

 

3. BFS를 구현해서 바이러스를 퍼뜨려보고, 안전지대 영역을 받아서 이전의 값과 비교하면서 값을 갱신한다.

 

4. 답이라면 그대로 출력하고, 답이 아니라면 map과 visit을 초기화해서 다른 위치에 벽을 세워본다.

 

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

int map[8][8];
int origin[8][8];//바꿔줄 맵
bool visit[8][8];//방문체크
vector<pair<int,int>>zeros;//
vector<int>temp;//조합을 위한,전체에서 3개를 1로만들기
int m, n;
int spread(vector<int>temp);
void bfs(int i, int j);
int ans;
int dx[4] = { -1,+1,0,0 };
int dy[4] = { 0,0,-1,+1 };

int main() {
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >>origin[i][j];
			map[i][j] = origin[i][j];
			if (origin[i][j] == 0) {
				zeros.push_back(make_pair(i, j));//0인애 위치저장
			}
		}
	}


	for (int i = 0; i < zeros.size()-3; i++)
		temp.push_back(0);
	for (int i = 0; i < 3; i++)
		temp.push_back(1);

	do {
		int result = spread(temp);
		//퍼뜨린 결과로 답 수정
		ans = max(result, ans);
		//되돌리기(방문체크랑 map고치기)
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j] = origin[i][j];
				visit[i][j] = false;
			}
		}
	} while (next_permutation(temp.begin(), temp.end()));

	cout << ans;
	return 0;
}

int spread(vector<int>temp) {
	int result=0;

	//3개의 벽 세우기
	for (int i = 0; i < temp.size(); i++) {
		if (temp[i] == 1) {
			int x = zeros[i].first; int y = zeros[i].second;
			map[x][y] = 1;
		}
	}

	//바이러스 퍼뜨리는 코드
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 2 && !visit[i][j]) {
				bfs(i, j);
			}
		}
	}
	//안전지대 세서 리턴하는 코드(퍼뜨린 뒤 0인 개수)
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 0)
				result++;
		}
	}

	

	
	return result;
}

void bfs(int i, int j) {
	queue<pair<int, int>>q;
	q.push(make_pair(i, j));
	visit[i][j] = true;

	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 (-1 < nx && nx < m && -1 < ny && ny < n && !visit[nx][ny] && map[nx][ny] == 0) {
				q.push(make_pair(nx, ny));
				map[nx][ny] = 2;
				visit[nx][ny] = true;
			}
		}
	}
	return;
}