문제

BOJ 14502, 연구소

핵심

• 입력의 크기가 $8^2$이라 구현에 초점을 맞춘다.
• 연구소에 바이러스가 유출되었고, 바이러스를 막기 위해 최대 벽을 3개 설치할 수 있다. 바이러스가 퍼질 수 없게 벽을 세워 안전 영역 크기의 최댓값을 구해야 한다.
• 8 * 8 지도에 최소 바이러스가 2개 있다면, 최대 62개의 빈 공간 중 벽 3개를 선택하여 바이러스가 최소가 되는 경우를 구해야 한다. 물론 빈 곳에는 벽이 포함된다. 따라서 벽을 제외한 빈 공간에서 중복 없이 3개를 골라 벽을 만드는 조합에 관한 문제이다. 비어 있는 전체 공간 중 3개를 고르는 조합은 아래 코드처럼 작성할 수 있다.

void dfs(int depth, vector<pair<int, int>>& seq, vector<bool>& isSelected) {                   
	if (depth == 3) {¡
		// 벽을 3개를 세우고, 바이러스 전파하는 코드 필요
		return ;
	}
	for (int i = 0; i < (int)emp.size(); ++i) {
		if (isSelected[i])
			continue;
		isSelected[i] = true;
		seq.push_back(emp[i]);
		dfs(depth + 1, seq, isSelected);
		seq.pop_back();
		isSelected[i] = false;
	}
}

• 빈 공간을 벽으로 만들었다면 안전 영역이 최대가 되는 영역을 구하기 위해 bfs로 바이러스를 전파한다. 벽을 고른 각각의 경우에 대해 바이러스가 전파되지 않은 영역의 최대 크기를 구하면 된다.

for (int i = 0; i < (int)virus.size(); ++i)
	q.push(virus[i]);
// 바이러스 전파
while (!q.empty()) {
	auto [y, x] = q.front(); q.pop();
	for (int dir = 0; dir < 4; ++dir) {
		int ny = y + dy[dir];
		int nx = x + dx[dir];
		if (ny < 0 || ny >= n || nx < 0 || nx >= m)
			continue;
		if (tmp[ny][nx] != 0)
			continue;
		tmp[ny][nx] = 2;	
		q.push({ny, nx});
	}
}
// 안전 영역 크기 구하기
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);

개선

코드

시간복잡도

• 대략 $O(empty^3 \times n \times m)$

C++

#include <iostream>
#include <queue>
using namespace std;

int n, m;
int map[10][10];
vector<pair<int, int>> emp;
vector<pair<int, int>> virus;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
int ans = 0;
void bfs(vector<pair<int, int>>& seq) {
	int tmp[10][10];
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j)
			tmp[i][j] = map[i][j];
	}
	for (int i = 0; i < (int)seq.size(); ++i)
		tmp[seq[i].first][seq[i].second] = 1;;
	queue<pair<int, int>> q;
	for (int i = 0; i < (int)virus.size(); ++i)
		q.push(virus[i]);
	while (!q.empty()) {
		auto [y, x] = q.front(); q.pop();
		for (int dir = 0; dir < 4; ++dir) {
			int ny = y + dy[dir];
			int nx = x + dx[dir];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m)
				continue;
			if (tmp[ny][nx] != 0)
				continue;
			tmp[ny][nx] = 2;	
			q.push({ny, nx});
		}
	}
	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 dfs(int depth, vector<pair<int, int>>& seq, vector<bool>& isSelected) {
	if (depth == 3) {
		bfs(seq);
		return ;
	}
	for (int i = 0; i < (int)emp.size(); ++i) {
		if (isSelected[i])
			continue;
		isSelected[i] = true;
		seq.push_back(emp[i]);
		dfs(depth + 1, seq, isSelected);
		seq.pop_back();
		isSelected[i] = false;
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	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)
				emp.push_back({i, j});
			else if (map[i][j] == 2)
				virus.push_back({i, j});
		}
	}
	vector<bool> isSelected(8, 0);
	vector<pair<int, int>> seq;
	dfs(0, seq, isSelected);
	cout << ans;
}

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int n, m;
    static int[][] map = new int[10][10];
    static ArrayList<int[]> emp = new ArrayList<>();
    static ArrayList<int[]> virus = new ArrayList<>();
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};
    static int ans = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 0)
                    emp.add(new int[]{i, j});
                else if (map[i][j] == 2)
                    virus.add(new int[]{i, j});
            }
        }
        boolean[] isSelected = new boolean[emp.size()];
        dfs(0, new ArrayList<>(), isSelected);
        System.out.println(ans);
        br.close();
    }

    static void dfs(int depth, ArrayList<int[]> seq, boolean[] isSelected) {
        if (depth == 3) {
            bfs(seq);
            return;
        }
        for (int i = 0; i < emp.size(); i++) {
            if (isSelected[i])
                continue;
            isSelected[i] = true;
            seq.add(emp.get(i));
            dfs(depth + 1, seq, isSelected);
            seq.remove(seq.size() - 1);
            isSelected[i] = false;
        }
    }

    static void bfs(ArrayList<int[]> seq) {
        int[][] tmp = new int[n][m];
        for (int i = 0; i < n; i++)
            System.arraycopy(map[i], 0, tmp[i], 0, m);
        for (var e : seq)
            tmp[e[0]][e[1]] = 1;
        Queue<int[]> q = new LinkedList<>();
        for (var e : virus)
            q.add(e);
        while (!q.isEmpty()) {
            var cur = q.poll();
            for (int dir = 0; dir < 4; dir++) {
                int ny = cur[0] + dy[dir];
                int nx = cur[1] + dx[dir];
                if (ny < 0 || ny >= n || nx < 0 || nx >= m)
                    continue;
                if (tmp[ny][nx] != 0)
                    continue;
                tmp[ny][nx] = 2;
                q.add(new int[]{ny, nx});
            }
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (tmp[i][j] == 0)
                    cnt++;
            }
        }
        ans = Math.max(ans, cnt);
    }
}