14502: 연구소

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

14502번: 연구소

설명

안전 영역 크기의 최댓값을 구하는 문제이다. 벽을 3개 설치하는 모든 경우의 수를 다 계산해야한다. 전체 맵의 크기가 8x8 이므로 (3 ≤ N, M ≤ 8) 벽을 설치할 수 있는 모든 조합의 수는 최악의 경우(바이러스가 하나도 존재하지 않을 경우) 64Combination3이 될 것이다. 이는 100,000보다 작은 수 이므로, 모든 경우의 수를 고려해도 제한 시간 안에 해결 가능. 

핵심 아이디어

• 파이썬의 조합 라이브러리 활용 or DFS/BFS를 이용해서 해결 가능
• 벽의 개수가 3개가 되는 모든 조합을 찾은 뒤에 그러한 조합에 대해서 안전 영역의 크기를 계속 비교해 최댓값을 구하면 된다. 
• 초기에 비어있는 모든 공간 중에서 3개를 골라 벽을 설치한다. 매번 벽을 설치할 때마다, 각 바이러스가 사방으로 퍼지는 것을 DFS/BFS로 계산하여 안전영역을 구한다. 

안전 영역의 크기를 계산하는 함수 정의

def get_score():
    cnt = 0
    for i in range(n):
    	for j in range(m):
        	if temp[i][j] == 0:
            	cnt += 1
    return cnt # 안전 영역의 크기 비교를 위해 반환

벽을 설치하고 나서 바이러스가 퍼지는 로직을 dfs를 통해 한다.

def virus(x,y):
	for i in range(4):
    	nx = x + dx[i]
        ny = y + dy[i]
        # 만약 주어진 범위를 벗어나지 않고, 바이러스가 한번도 방문하지 않았다면
        if (0 <= nx < n) and (0 <= ny < n) and temp[i][j] == 0:
            # 바이러스 퍼진다.	
            temp[i][j] = 1
            # 재귀적 퍼지게한다.	
            virus(nx,ny)

이제 벽을 3개 설치하는 모든 경우의 수를 dfs를 통해 구현한다. 이때, 안전영역의 크기를 비교하는 로직 포함.

result = 0
def dfs(count): # count 는 벽의 수
	global result
	if count == 3: 벽을 3개 설치했다면
        for i in range(n):
            for j in range(m):
                temp[i][j] = graph[i][j] # 벽 3개 설치한 맵을 temp[i][j]에 임시저장. 
        # 이제 바이러스 퍼지게 하기
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2: # 바이러스가 있다면 퍼져!~
                    virus(i,j)
        # 바이러스가 퍼졌으면 안전 영역의 크기를 비교해서 갱신
        result = max(result, get_score())
        return
    else:
    	# 벽이 3개가 아니라면 벽을 설치한다.
        for i in range(n):
        	for j in range(m):
            	if graph[i][j] == 0:
                	graph[i][j] = 1  # 벽 설치
                    count += 1
                    # 재귀적으로 벽을 설치하기 위해 
                    dfs(count)
                    # 탐색 끝나면 다음 방향 탐색을 위해 다시 벽치운다.
                    graph[i][j] = 0
                    count -= 1

코드 구현

PyPy3 제출

n, m = map(int, input().split())
graph = []
for _ in range(n):
	graph.append(list(map(int, input().split())))

# 임시 맵 초기화
temp = [[0] * m for _ in range(n)]
# 바이러스가 상 하 좌 우 이동을 위한 방향 정의
dx = [-1,1,0,0]
dy = [0,0,-1,1]
# 바이러스가 퍼진 후 안전 영역의 크기를 구하는 함수 정의
# 이는 벽 3개 설치했다는 가정하에 진행 따라서 임시맵 사용
def get_score():
	cnt = 0
	for i in range(n):
		for j in range(m):
			if temp[i][j] == 0:
				cnt += 1
	return cnt # 안전 영역의 크기 반환
# dfs를 통해 바이러스 퍼지는 함수 정의
# 이는 벽이 3개 다 설치하고 난 후 진행한다는 가정
def virus(x,y):
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		# 만약 주어진 범위를 벗어나지 않고, 바이러스가 방문한 적이 없다면
		if (0 <= nx < n) and (0 <= ny < m) and temp[nx][ny] == 0:
			# 해당 위치에 바이러스 퍼지게 한다.
			temp[nx][ny] = 1
			virus(nx,ny) # 재귀적으로 방문
# 이제 벽을 3개 설치하는 모든 경우의 수를 dfs를 통해 구현한다.
ans = 0
def dfs(count): # count는 벽의 수
	global ans
	if count == 3: # 벽 3개 설치했다면
		for i in range(n):
			for j in range(m):
				# 임시맵에 벽 설치한 맵을 임시로 대입
				temp[i][j] = graph[i][j]
		# 각 바이러스 퍼지게 한다.
		for i in range(n):
			for j in range(m):
				if temp[i][j] == 2: # 바이러스가 있는 위치
					virus(i,j) # 바이러스 퍼지게한다.
		# 바이러스 다퍼졌으면 안전 영역의 크기 구해서 비교한다.
		# 최댓값으로 갱신한다.
		ans = max(ans, get_score())
		return
	else: # 벽이 아직 3개가 설치 되지 않았다면
		# 벽을 설치한다.
		for i in range(n):
			for j in range(m):
				if graph[i][j] == 0:
					graph[i][j] = 1 # 벽을 설치
					count += 1
					# 재귀적으로 반복
					dfs(count)
					# 재귀가 끝난 후 다음 벽 설치를 위해 벽 제거
					graph[i][j] = 0
					count -= 1
# 함수 수행
dfs(0) # 처음에는 벽이 0이라고 설정
print(ans)

C++

#include <iostream>

using namespace std;

int n, m;
int graph[8][8]; // 초기 맵 배열
int temp[8][8]; // 벽을 설치한 뒤의 맵 배열

// 4가지 이동 방향에 대하여
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};

// 바이러스 퍼지는 함수 정의
void virus(int x, int y) { // 바이러스 좌표 들어온다.
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (0 <= nx && nx < n && 0 <= ny && ny < m) {
			if (temp[nx][ny] == 0) {
				// 해당 위치에 바이러스 배치하고, 다시 재귀적 수행
				temp[nx][ny] = 2;
				virus(nx, ny);
			}
		}
	}
}

// 안전 영역의 크기를 구하는 함수 정의
int get_score() {
	int score = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (temp[i][j] == 0) {
				score += 1;
			}
		}
	}
	return score;
}

// dfs 알고리즘을 통해 벽 설치하면서, 매번 안전영역 크기 계산
int ans = 0;
void dfs(int count) {
	if (count == 3) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				temp[i][j] = graph[i][j];
			}
		}
		// 각 바이러스의 위치에서 퍼진다.
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (temp[i][j] == 2) {
					virus(i, j);
				}
			}
		}
		ans = max(ans, get_score());
		return;
	}
	// 빈 공간에 울타리 설치
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (graph[i][j] == 0) {
				graph[i][j] = 1; // 벽을 설치
				count += 1;
				dfs(count);
				graph[i][j] = 0;
				count -= 1;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> graph[i][j];
		}
	}
	dfs(0);
	cout << ans << "\n";

}