백준 14502 연구소

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

 

서론

완전탐색 +  DFS/BFS

삼성문제들은 완전탐색, DFS/BFS, 시뮬레이션 안에서만 출제되는거 같다.

 

---

풀이

지도를 입력받으면서 바이러스는 따로 벡터에 좌표를 저장한다.

 

가벽을 3개 세우는 모든 경우의 수를 찾기 위해 완전탐색을 이용한다.

가벽을 3개 세웠으면 바이러스를 퍼뜨리기 위해 DFS를 이용한다.

그 후 바이러스가 퍼지지 않은곳들을 세어본다.

void bf(int idx, int y, int x){
    if(map[y][x] > 0) return; // 바이러스거나 벽이면 리턴
    map[y][x] = 3; // 가벽은 3으로 마크
    
    if(idx == 2){ // 가벽을 3개 세웠다면
    	for(i : virus) dfs(i); // 모든 바이러스들을 dfs로 퍼뜨린다.
        sum = cal(); // 바이러스가 없는 칸의 개수를 리턴
    	result = max(result, sum); // 최대값을 출력하기 위함
        map[y][x] = 0; // 가벽제거
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
    		bf(idx + 1, i, j); // 완전탐색
        }
    }
    map[y][x] = 0;
    return;
}

 

---

구현

// c++

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int map[8][8];
int visited[8][8];
int result;
int n, m;
vector <pair<int, int>>virus;
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };

void init() {
	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] == 2)virus.push_back({ i,j });
		}
	}
}

void dfs(int y, int x) {
	if (visited[y][x] > 0) return;

	visited[y][x] = 1;

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < n && nx < m && ny >= 0 && nx >= 0 && map[ny][nx] == 0 && visited[ny][nx] == 0) {
			dfs(ny, nx);
		}
	}

	return;
}

void bf(int idx, int y, int x) {
	if (map[y][x] > 0) return;

	map[y][x] = 3; // 가벽은 3

	if (idx == 2) {
		/*
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				cout << map[i][j];
			}
			cout << endl;
		}
		cout << endl;
		*/
		
		for (int i = 0, size = virus.size(); i < size; i++) {
			dfs(virus[i].first, virus[i].second);
		}

		int sum = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 0 && visited[i][j] == 0) sum++;
			}
		}
		result = max(result, sum);

		memset(visited, 0, sizeof(visited));
		map[y][x] = 0;
		return;
		
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			bf(idx + 1, i, j);
		}
	}
	
	map[y][x] = 0;
	return;
}

int main() {
	init();
	bf(-1, -1, -1);
	cout << result;
}