[백준 JAVA]14502_연구소

[문제 링크] 14502 boj 연구소 자바 

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

14502번: 연구소

[생각 흐름]

문제는 연구실에 바이러스가 최대한 안 퍼지게 할 수 있는 벽을 3개 세우는 문제이다.

처음에는 모든 경우에 3개 벽을 세우는 것을 계산하여 문제를 푸는 것인지 고민했다 (설마 완탐..? )

예제를 보다가 내가 계산하는 것도 어렵게 느껴져서 그냥 완탐으로 풀이하였다.

일단 백 트랙킹을 이용하여 벽을 3개 어떻게 세울 건지 고려하고, 각각의 경우에 대해서 바이러스가 퍼지는 경우

몇 개의 칸에 바이러스가 퍼지지 않는지 계산하여 최댓값을 계산하여 출력하였다.

 

[코드]

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    private static int arr[][];
    private static int cob[] = new int[3];
    private static boolean visit[];
    private static ArrayList<Point> none = new ArrayList<>();
    private static ArrayList<Point> virus = new ArrayList<>();
    private static int max = 0;

    public static void combination(int start, int d) {
        if (d == 3) {
            check();
            return;
        }
        for (int i = start; i < none.size(); i++) {
            if (!visit[i]) {
                visit[i] = true;
                cob[d] = i;
                combination(i, d + 1);
                visit[i] = false;
            }
        }
    }

    private static void check() {
        int arrc[][] = new int[arr.length][arr[0].length];

        for(int i=0;i<arr.length;i++) 
            arrc[i]=arr[i].clone();

        for(int k :cob){
            Point temp = none.get(k);
            arrc[temp.x][temp.y]=1;
        }


        int dirx[] = new int[]{-1, 1, 0, 0};
        int diry[] = new int[]{0, 0, -1, 1};
        Queue<Point> q = new LinkedList<>();
        for( Point a : virus) q.add(a);

        while (!q.isEmpty()) {
            Point temp = q.poll();
            int px = (int) temp.getX();
            int py = (int) temp.getY();

            for (int i = 0; i < 4; i++) {
                int nx = px + dirx[i];
                int ny = py + diry[i];

                //벗어남
                if (nx >= arrc.length || nx < 0 || ny < 0 || ny >= arrc[0].length) continue;

                //벽이거나 이미 바이런스 감염된 경우
                if (arrc[nx][ny] == 1 || arrc[nx][ny] == 2) continue;

                //방문안한 노드이면
                if (arrc[nx][ny] == 0) {
                    arrc[nx][ny] = 2;
                    q.add(new Point(nx, ny));
                }
            }
        }


       int tmp=0;

       for(int i=0;i<arrc.length;i++){
           for(int j=0;j<arrc[0].length;j++){
               if(arrc[i][j]==0) tmp++;
           }
       }

       max = Math.max(tmp,max);

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int row = Integer.parseInt(st.nextToken());
        int col = Integer.parseInt(st.nextToken());

        arr = new int[row][col];
        //입력구간
        for (int i = 0; i < row; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < col; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] == 0) none.add(new Point(i, j));
                else if(arr[i][j]==2) virus.add(new Point(i,j));
            }
        }
        //나올 수 있는 경우의 수
        visit = new boolean[none.size()];
        combination(0, 0);
        System.out.println(max);

    }
}