백준 14502 연구소 (Java,자바)

jonghyukLee·2022년 2월 7일

이번에 풀어본 문제는
백준 14502번 연구소 입니다.

📕 문제 링크

❗️코드

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

class Virus
{
    int x,y;

    public Virus(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
public class Main {
    static int [][] origin;
    static List<Virus> virus;
    static int N,M;
    static int wall_cnt = 3;
    static int total_area;
    static int answer = Integer.MIN_VALUE;
    static int [] dx = {-1,1,0,0};
    static int [] dy = {0,0,-1,1};
    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());
        total_area = N * M;

        origin = new int[N][M];
        virus = new ArrayList<>();

        for(int i = 0; i < N; ++i)
        {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; ++j)
            {
                int next = Integer.parseInt(st.nextToken());
                origin[i][j] = next;
                if(next == 2) virus.add(new Virus(i,j));
                else if(next == 1) wall_cnt++;
            }
        }

        makeWall(0);
        System.out.println(answer);
    }
    static void makeWall(int cnt)
    {
        if(cnt == 3)
        {
            spread();
            return;
        }

        for(int i = 0; i < N; ++i)
        {
            for(int j = 0; j < M; ++j)
            {
                if(origin[i][j] == 0)
                {
                    origin[i][j] = 1;
                    makeWall(cnt+1);
                    origin[i][j] = 0;
                }
            }
        }
    }
    static void spread()
    {
        int [][] copy_map = new int[N][M];

        for(int i = 0; i < N; ++i)
        {
            System.arraycopy(origin[i],0,copy_map[i],0,M);
        }

        Queue<Virus> q = new LinkedList<>(virus);
        int virus_area = 0;
        while(!q.isEmpty())
        {
            Virus cur = q.poll();
            virus_area++;
            for(int idx = 0; idx < 4; ++idx)
            {
                int mx = cur.x + dx[idx];
                int my = cur.y + dy[idx];

                if(!isValid(mx,my)) continue;
                if(copy_map[mx][my] == 0)
                {
                    copy_map[mx][my] = 2;
                    q.add(new Virus(mx,my));
                }
            }
        }
        answer = Math.max(answer,total_area - (wall_cnt + virus_area));
    }
    static boolean isValid(int x, int y)
    {
        return x >= 0 && y >= 0 && x < N && y < M;
    }
}

📝 풀이

사방으로 퍼지는 바이러스가 있을 때, 벽을 3개 추가하여 만들 수 있는 안전영역의 최댓값을 구하는 문제입니다. 벽과 바이러스가 퍼진 칸을 제외한 모든 칸을 안전영역이라 합니다.
먼저 makeWall에서 map[0][0] 으로부터 빈칸을 만났을 때, 해당 인덱스에 기둥을 세우고, 카운트를 증가시킨 함수를 재귀 호출하는 dfs함수를 통해 기둥을 세울 수 있는 모든 경우의 수를 체크했습니다. 카운트가 3인 상태로 넘어왔다면, 기둥을 모두 세운 상태이므로 spread함수로 넘긴 후 종료합니다.
spread에서는 바이러스를 퍼뜨려, 안전영역의 범위를 구해줍니다.
먼저 기존 맵이 변경될 수 있기 때문에, copy_map에 원본을 복사해주고, 복사된 맵에서 bfs 탐색을 수행하여 바이러스가 퍼진 칸의 갯수를 구해줍니다.
마지막으로 (전체 맵의 크기 - (벽의 갯수 + 바이러스가 퍼진 칸수)) 를 해주면 해당 경우에서의 안전영역의 크기를 구할 수 있습니다. 최댓값을 answer에 담아 출력해주면 해결됩니다.