BOJ 14502 - 연구소

14502번: 연구소 (acmicpc.net)

14502번: 연구소

 

이번 문제는 DFS와 브루트 포스를 이용하여 풀 수 있는 문제이다.

실행시간도 2초라 널널할 것 같아 다음과 같이 풀었다.

 

알고리즘은 다음과 같다.

 

1. 빈 칸(0) 중 3곳을 골라 벽(1)을 세운다.

2. 벽을 세운 상태에서, 바이러스(2)들을 그래프탐색 시키며 지나간곳을 체크한다.

3. 바이러스가 지나가지 않았고, 벽이 아닌 곳의 수가 가장 큰 값을 구한다.

 

간단하게 해결할 수 있는 문제이다. 

visited[10][10]을 이용하여, 빈 칸은 0 / 벽은 1 / 바이러스가 지나간 곳은 2 로 정하고 코딩하였다.

 

코드

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

#define MAX 10

using namespace std;

int n, m;
int res = 0;
int map[MAX][MAX];
// 1: 벽, 2: 바이러스
int visited[MAX][MAX];
vector<pair<int, int>> virus;
vector<pair<int, int>> empties;

int xPos[4] = { -1,0,1,0 };
int yPos[4] = { 0,-1,0,1 };

void init() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			visited[i][j] = map[i][j];
		}
	}
}

void dfs(int x, int y) {
	
	visited[x][y] = 2;

	for (int i = 0; i < 4; i++) {
		int movedX = x + xPos[i];
		int movedY = y + yPos[i];
		
        if (movedX < 0 || movedY < 0 || movedX >= n || movedY >= m) continue;
		
		if (visited[movedX][movedY] == 0)
			dfs(movedX, movedY);
	}	
}

// 바이러스 순서대로 DFS 진행!
void check() {

	for (int i = 0; i < virus.size(); i++) {
		dfs(virus[i].first, virus[i].second);
	}

	// 카운팅하기
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if(visited[i][j] == 0)
				cnt++;
		}
	}

	// res에 빈 칸의 수가 가장 클 때를 저장한다.
	res = max(res, cnt);
	
}

void chooseWall(int idx1, int idx2, int idx3) {
	pair<int, int> wall1 = empties[idx1];
	pair<int, int> wall2 = empties[idx2];
	pair<int, int> wall3 = empties[idx3];

	visited[wall1.first][wall1.second] = 1;
	visited[wall2.first][wall2.second] = 1;
	visited[wall3.first][wall3.second] = 1;

	// 각 바이러스들을 그래프 탐색 시킨다.
	check();
    // 체크 완료 후, 원상복구 시킨다.
	init();

	visited[wall1.first][wall1.second] = 0;
	visited[wall2.first][wall2.second] = 0;
	visited[wall3.first][wall3.second] = 0;
}

int main() {
	int tmp;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0)
				empties.push_back(make_pair(i, j));
			else if (map[i][j] == 2)
				virus.push_back(make_pair(i, j));
		}
	}

	init();

	for (int i = 0; i < empties.size()-2; i++) {
		for (int j = i+1; j < empties.size()-1; j++) {
			for (int k = j+1; k < empties.size(); k++) {
				if (i != j && j != k) {
					chooseWall(i, j, k);
				}
			}
		}
	}

	cout << res;
}