boj 14502 연구소

www.acmicpc.net/problem/14502

14502번: 연구소

연구소에 벽 3개를 설치하여 바이러스로부터 안전 영역의 크기를 최대로 해야합니다.

이 문제는 브루트포스 방식과 bfs를 사용하여 해결하였습니다.

 

브루트포스로 설치할 벽의 모든 경우를 구하였고, 3개의 벽을 설치하면 bfs를 돌려서 바이러스를 최대한 퍼뜨린 후에 안전 영역의 갯수를 구하였습니다.

 

 

[C++]

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
 
queue<pair<int, int> > q;
int direct[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } };
bool visit[8][8];
int list[8][8];
int N, M, ans;
 
void bfs() {
    queue<pair<int, int> > nq = q;
    int sum = 0;
    while (!nq.empty()) {
        int x = nq.front().first;
        int y = nq.front().second;
        nq.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];
            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (list[nx][ny] != 0 || visit[nx][ny]) continue;
            visit[nx][ny] = true;
            nq.push({ nx,ny });
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (list[i][j] != 0 || visit[i][j]) continue;
            sum++;
        }
    }
 
    ans = max(ans, sum);
}
 
void func(int x, int y, int cnt) {
    if (cnt == 3) {
        bfs();
        memset(visit, false, sizeof(visit));
        return;
    }
 
    int sx = x;
    int sy = y;
    for (int i = sx; i < N; i++) {
        for (int j = sy; j < M; j++) {
            if (list[i][j] != 0) continue;
 
            list[i][j] = 1;
            if (j == M - 1) func(i + 1, 0, cnt + 1);
            else func(i, j + 1, cnt + 1);
            list[i][j] = 0;
        }
        sy = 0;
    }
}
 
void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> list[i][j];
 
            if (list[i][j] == 2) {
                q.push({ i,j });
                visit[i][j] = true;
            }
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func(0, 0, 0);
    cout << ans << '\n';
 
    return 0;
}

 

 

[Java]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int list[][] = new int[8][8];
    static Deque<int[]> virus = new ArrayDeque<>();
    static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
    static int N, M, ans;
 
    static void bfs() {
        Deque<int[]> dq = new ArrayDeque<>();
        boolean visit[][] = new boolean[8][8];
        dq.addAll(virus);
        Iterator<int[]> iter = dq.iterator();
        while (iter.hasNext()) {
            int xy[] = iter.next();
            visit[xy[0]][xy[1]] = true;
        }
 
        while (!dq.isEmpty()) {
            int x = dq.peek()[0];
            int y = dq.poll()[1];
 
            for (int i = 0; i < 4; i++) {
                int nx = x + direct[i][0];
                int ny = y + direct[i][1];
 
                if (nx < 0 || ny < 0 || nx >= N || ny >= M)
                    continue;
                if (visit[nx][ny] || list[nx][ny] == 1)
                    continue;
 
                dq.add(new int[] { nx, ny });
                visit[nx][ny] = true;
            }
        }
 
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (visit[i][j] || list[i][j] != 0)
                    continue;
 
                cnt++;
            }
        }
 
        ans = Math.max(ans, cnt);
    }
 
    static void func(int sx, int sy, int cnt) {
        if (cnt == 3) {
            bfs();
            return;
        }
 
        int i = sx;
        int j = sy;
        for (; i < N; i++) {
            for (; j < M; j++) {
                if (list[i][j] != 0)
                    continue;
 
                list[i][j] = 1;
                if (j == M - 1)
                    func(i + 1, 0, cnt + 1);
                else
                    func(i, j + 1, cnt + 1);
                list[i][j] = 0;
            }
            j = 0;
        }
    }
 
    static void input() throws Exception {
        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++) {
                list[i][j] = Integer.parseInt(st.nextToken());
                if (list[i][j] == 2) {
                    virus.add(new int[] { i, j });
                }
            }
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func(0, 0, 0);
        System.out.println(ans);
    }
}