[BOJ 14502] 연구소 (Java, Python)

문제

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

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

 

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다. 벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

 

풀이

Brute Force + BFS 조합으로 풀었다. 

1. 빈 칸 좌표 중에 3개를 뽑는 조합을 재귀함수로 구현한다. 

2. 3개를 뽑은 후에 BFS 알고리즘으로 바이러스를 확산 시킨다.

(맵을 재활용해야 하므로 바이러스 확산 시 사용할 map은 clone하여 넘겨주었다. )

3. 안전 영역의 개수를 카운트하여 max값과 비교하여 값이 더 크다면 갱신 한다. 

 

소스코드

package bfs;

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

public class BOJ14502 {
    public static int[][] map;
    public static int[][] dir = new int [][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public static int N, M, answer;
    public static ArrayList<int[]> zeroList;
    public static ArrayList<int[]> twoList;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        answer = Integer.MIN_VALUE;
        map = new int[N][M];
        zeroList = new ArrayList<int[]>();
        twoList = new ArrayList<int[]>();

        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) zeroList.add(new int[]{i, j});
                if(map[i][j] == 2) twoList.add(new int[]{i, j});
            }
        }

        // 빈 칸 중에 3 개 뽑아서 bfs하기
        recur(0, 0);

        System.out.println(answer);
    }

    public static int countZero(int[][] temp){
        int count = 0;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(temp[i][j] == 0) count++;
            }
        }
        return count;
    }

    public static int[][] clone(int[][] map){
        int[][] temp = new int[N][M];
        for(int i = 0; i < N; i++){
            temp[i] = map[i].clone();
        }
        return temp;
    }

    public static void recur(int idx, int k){
        if(k == 3){
            // map clone
            int[][] temp = clone(map);
            for(int[] virus : twoList){
                bfs(temp, virus[0], virus[1]);
            }
            answer = Math.max(answer, countZero(temp));
            return;
        }
        for(int i = idx; i < zeroList.size(); i++){
            int[] zero = zeroList.get(i);
            int x = zero[0];
            int y = zero[1];
            if(map[x][y] == 1) continue;
            map[x][y] = 1;
            recur(i+1, k+1);
            map[x][y] = 0;
        }
    }

    public static void bfs(int[][] temp, int sx, int sy){
        Queue<Integer> que = new LinkedList<Integer>();
        que.offer(sx);
        que.offer(sy);

        while(!que.isEmpty()){
            int x = que.poll();
            int y = que.poll();
            for(int[] d : dir){
                int nx = x + d[0];
                int ny = y + d[1];
                if(isValid(temp, nx, ny)){
                    temp[nx][ny] = 2;
                    que.offer(nx);
                    que.offer(ny);
                }
            }
        }
    }

    public static boolean isValid(int[][] temp, int x, int y){
        if(x < 0 || y < 0 || x >= N || y >= M) return false;
        if(temp[x][y] != 0) return false;
        return true;
    }
}

 

Python

from itertools import combinations
from collections import deque
import copy

n, m = map(int, input().split())

center = [[0] * (m+1) for _ in range(n+1)]
viruses = []
blanks = []

direction = [(-1, 0), (1, 0), (0, 1), (0, -1)]
answer = 0

def bfs(center, viruses):
    global answer

    que = deque()
    # 초기 바이러스
    for virus in viruses:
        que.append(virus)

    while que:
        cx, cy = que.popleft()
        for dir in direction:
            nx = cx + dir[0]
            ny = cy + dir[1]
            if nx <= 0 or ny <= 0 or nx > n or ny > m or center[nx][ny] == 1 or center[nx][ny] == 2:
                 continue
            que.append((nx, ny))
            center[nx][ny] = 2

    answer = max(answer, calculate_safetyzone(center))


def calculate_safetyzone(center):
    count = 0
    global n, m
    for i in range(1, n+1):
        for j in range(1, m+1):
            if center[i][j] == 0:
                count += 1
    return count

for i in range(1, n+1):
    data = list(map(int, input().split()))
    for j in range(1, m+1):
        center[i][j] = data[j-1]
        if data[j-1] == 0:
            blanks.append((i, j))
        elif data[j-1] == 2:
            viruses.append((i, j))

# 벽 3개를 세울 좌표 조합을 구해야 함
walls_list = list(combinations(blanks, 3))
for walls in walls_list:
    mock_center = copy.deepcopy(center)

    for wall in walls:
        # 벽 3개 설치
        wx, wy = wall[0], wall[1]
        mock_center[wx][wy] = 1
    bfs(mock_center, viruses)

print(answer)