[java 백준] 골드 5/ 14502번 연구소

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
 
    public static int N;
    public static int M;
 
    public static int [][]arr;
    public static boolean visited[][];
    public static int [][]ans;
 
    public static int dirX[]={-1,1,0,0};
    public static int dirY[]={0,0,-1,1};
 
 
    public static int result=Integer.MIN_VALUE;
 
    public static class Node{
        int x,y;
        public Node(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
 
 
    //바이러스 퍼뜨리기 (BFS)
 
    public static void BFS(){
        ans=new int[N][M];
        Queue<Node>queue=new LinkedList<Node>();
 
        //원본 배열 카피 (손실 안되게)
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                ans[i][j]=arr[i][j];
            }
        }
 
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(ans[i][j]==2){
                    queue.add(new Node(i,j));
                }
            }
        }
 
        while(!queue.isEmpty()){
 
            Node node=queue.poll();
            for(int s=0;s<4;s++){
                int nX=node.x+dirX[s];
                int nY=node.y+dirY[s];
 
                if(nX>=0&&nX<N&&nY>=0&&nY<M){
                    if(ans[nX][nY]==0){
 
                        queue.add(new Node(nX,nY));
                        ans[nX][nY]=2;
                    }
                }
            }
 
        }
 
        getScore(ans);
    }
 
    //안전영역의 크기를 계산
 
    public static void getScore(int[][]ans){
        int score=0;
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(ans[i][j]==0){
                    score++;
                }
            }
        }
 
        result=Math.max(result,score);
 
    }
    
    //울타리 설치하면서 안전영역 계산
    public static void DFS(int depth){
 
        if(depth==3){
            BFS();
            return;
        }
 
        
        //울타리 넣어주기
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(arr[i][j]==0){
                    arr[i][j]=1;
 
 
                    DFS(depth+1);
                    //백트래킹 느낌 
                    arr[i][j]=0;
 
 
                }
            }
        }
 
 
 
    }
 
 
    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());
        arr=new int[N][M];
        visited=new boolean[N][M];
 
 
        for(int i=0;i<N;i++){
 
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
 
                arr[i][j]=Integer.parseInt(st.nextToken());
 
            }
        }
 
        DFS(0);
        System.out.println(result);
 
 
 
    }
 
 
 
}

 

문제를 풀어갈 때 생각의 절차

 

1. 울타리를 세워주기 위한 DFS 탐색

2. 울타리를 세워줬으면 BFS를 통해 바이러스 퍼뜨리기 -> 이때 울타리만 세워준 원본 배열에 손실이 가지 않게 copy배열 만들기

3. 안전영역 크기 계산

 

3개에 해당하는 메서드를 만들면 된다. 

 

문제 풀면서 실수한 부분

 

재귀가 깊어지지 않게 조건 조심, 매개변수 오타 조심.