BOJ 14502 연구소(JAVA) 🧪

문제 링크

14502번: 연구소

문제 설명

벽 3개를 설치해 바이러스가 가장 적은 상태(안전 영역이 큰 상태)에서의 안전 영역의 크기를 구하는 문제

 

입력

N×M의 맵이 주어진다.

이때 0은 빈칸, 1은 벽, 2는 바이러스 

출력

바이러스가 가장 적은 상태(안전 영역이 큰 상태)에서의 안전 영역의 크기를 출력

즉, map에서의 '0' 개수 

 

구조화

0(빈칸)에 벽 세우고 안전 영역 크기 체킹, 벽은 3개만 세울 수 있음

=> 0(빈칸)에서 3개의 조합

 

sudo 코드

1. 0(빈칸) 중에 3개를 골라 벽을 세워보고 => 조합

2. 안전 영역 크기 체크(1마주치면 stop)

3. 이때 가장 큰 안전 영역이면 됨

 

소스 코드

package day0912;

import java.io.*;
import java.util.*;

/*
 * 0 중에 3개를 골라 1로 만듦 -> 조합
 * 
 */

public class Main_14502_연구소 {

    static int N, M; 
    static int max = Integer.MIN_VALUE;
    static int[][] map, copy;
    static int[] visited;
    // 상하좌우
    static int[][] way = {{-1,0},{1,0},{0,-1},{0,1}};
    static List<int[]> virus = new ArrayList<int[]>(); 

    public static void main(String[] args) throws NumberFormatException, 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());

        map = new int[N][M];
        copy = new int[N][M];

        visited = new int[3];
        for (int i = 0; i < N; i++) 
        {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) 
            {
                int val = Integer.parseInt(st.nextToken());
                map[i][j] = val;
                copy[i][j] = val;

                if(map[i][j] == 2)
                    virus.add(new int[] {i,j});
            }
        }

        combi(0, 0);

        System.out.println(max);

    }

    private static void CountZero() {

        int sum = 0;

        for (int i = 0; i < N; i++) 
        {
            for (int j = 0; j < M; j++) 
            {
                if(map[i][j] == 0)
                {
                    sum++;
                }
            }
        }

        max = max<sum?sum:max;

    }

    private static void PrintMap() {

        for (int[] is : map) 
        {
            System.out.println(Arrays.toString(is));
        }

    }

    static void PollVirus()
    {

        for (int i = 0; i < virus.size(); i++) {
            int x = virus.get(i)[0];
            int y = virus.get(i)[1];
            SpreadVirus(x, y);
        }    

    }

    static void SpreadVirus(int x, int y) 
    {

        int nx = 0, ny = 0;

        for (int w = 0; w < 4; w++) 
        {
            nx = x + way[w][0];
            ny = y + way[w][1];
            if (nx >= 0 && nx < N && ny >= 0 && ny < M && map[nx][ny] == 0) {
                map[nx][ny] = 2;
                SpreadVirus(nx, ny);

            }
        }

    }


    static void combi(int cnt, int start)
    {
        if(cnt == 3)
        {
            // 3개가 뽑혔다면        
            for (int i = 0; i < 3; i++) 
            {
                map[visited[i]/M][visited[i]%M] = 1;
            }

            PollVirus();
            CountZero();


            // 다시 되돌리기
            for (int i = 0; i < N; i++) 
            {
                for (int j = 0; j < M; j++) 
                {
                    map[i][j] = copy[i][j];
                }
            }

            return;
        }

        for (int i = start; i < N*M; i++) 
        {
            if(map[i/M][i%M]==0)
            {
                visited[cnt]=i;
                combi(cnt+1, i+1);
            }
        }
    }

}