알고리즘81 :: BOJ_18809_Gaaaaaaaaaarden(작성중)

package backjun;
 
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 backjun_18809_Gaaaaaaaaaarden {
 
    static int[][] map;
    static int[][] pre_map;
    static int[] visit;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static int G, R;
    static int x, y;
    static int rearAns = Integer.MIN_VALUE;
    static class POS {
        int x; 
        int y;
        POS(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    static class TIME{
        int x;
        int y;
        int time;
        int nextNumber;
        TIME(int x, int y, int time, int nextNumber){
            this.x = x;
            this.y = y;
            this.time = time;
            this.nextNumber = nextNumber;
        }
    }
    static ArrayList<POS> al = new ArrayList<>();
    static Queue<TIME> q = new LinkedList<>();
    
    static void cultureFluidGreen(int nn, int index) {
        if(nn==G) {
            cultureFluidRed(0,0);
            //print(pre_map); 정상 작동
            
            
        }else {
            for(int i=index; i<al.size(); i++) {
                //배양액을 뿌릴 수 있는 개수 만큼 돌아보고
                if(visit[i] == 0) {
                    visit[i] = 1;
                    int gx = al.get(i).x;
                    int gy = al.get(i).y;
                    pre_map[gx][gy] = 3; //초록색은 3으로 지정한다. 
                    cultureFluidGreen(nn+1, i+1);
                    pre_map[gx][gy] = map[gx][gy];
                    visit[i] = 0;
                }
            }
        }
    }
 
    static void cultureFluidRed(int nn, int index) {
        if(nn==R) {
            makeFlower();
            //print(pre_map); 정상 작동
        }else {
            for(int i=index; i<al.size(); i++) {
                if(visit[i] == 0) {
                    visit[i] = 1;
                    int rx = al.get(i).x;
                    int ry = al.get(i).y;
                    pre_map[rx][ry] = 4; //레드는 4으로 지정한다.
                    cultureFluidRed(nn+1, i+1);
                    pre_map[rx][ry] = map[rx][ry];
                    visit[i] = 0;
                }
            }
        }
    }
    static void cultureFluidInsertQueue() {
        for(int i=0; i<x; i++) {
            for(int j=0; j<y; j++) {
                if(pre_map[i][j] == 3)
                    q.add(new TIME(i,j,1,3));
                
                if(pre_map[i][j] == 4)
                    q.add(new TIME(i,j,1,4));
                }//end of if 
            }//end of for
        }//end of function
    
    static void makeFlower() {
        cultureFluidInsertQueue();
        
        int[][] temp = new int[x][y];
        for(int i=0; i<x; i++) { for(int j=0; j<y; j++) temp[i][j] = pre_map[i][j]; }
        
        int judgeMent = 2;
        int flower = 0;
        
        while(!q.isEmpty()) {
            TIME t = q.poll(); 
            int goX = t.x;
            int goY = t.y;
            int time = t.time;
            int nextNumber = t.nextNumber;
            //배양액은 갈 수 가 있음,
            //호수는 갈 수 가 없음 (호수 : 0)
            if(pre_map[goX][goY]==5) continue;
            
            for(int i=0; i<4; i++) {
                int nx = goX+dx[i];
                int ny = goY+dy[i];
                
                if(nx<0 || ny<0 || nx>=x || ny>=y) continue; //범위 밖은 아웃 ! 
                
                if(pre_map[nx][ny] == 0) continue;  //호수 인곳도 아웃 !
                
                if(pre_map[nx][ny] == 3 || //3 = 그린  
                   pre_map[nx][ny] == 4    || //4 = 레드 
                   pre_map[nx][ny] == 5  //5 = 꽃 
                ) continue; //이미 레드 이거나 그린이면 갈 수 없음, 꽃인 경우도 탈
                
                if(nextNumber ==3 && pre_map[nx][ny] == -2) continue;
                if(nextNumber ==4 && pre_map[nx][ny] == -1) continue;
                
                if(nextNumber == 3 && pre_map[nx][ny] == -1) {
                    //현재 배양액의 색깔 그린 이고 현재 퍼져 있는 배양의 색깔이 레드라면 꽃을 피운다.
                    
                    pre_map[nx][ny] = 5; 
                    ++flower;
                    continue;
                }
                
                if(nextNumber == 4 && pre_map[nx][ny] == -2) {
                    //현재 배양액의 색깔이 레드 이고 현재 퍼져 있는 배양액의 색깔이 초록이라면 꽃을 피운다. 
                    pre_map[nx][ny] = 5; 
                    ++flower;
                    continue;
                }
                
                if(nextNumber == 3 && pre_map[nx][ny]!=0) {
                    //초록색 
                    
                    pre_map[nx][ny] = -2;
                    q.add(new TIME(nx,ny,time+1,nextNumber));
                }
                
                if(nextNumber == 4 && pre_map[nx][ny]!=0) {
                    //빨간색 
                
                    pre_map[nx][ny] = -1;
                    q.add(new TIME(nx,ny,time+1,nextNumber));
                }
                
                
            }//end of for loop
            //한번 이동하고 잠깐 대, 그 다음 턴부터는 대기한게 굳어져 버리는 취지
            
            if(!q.isEmpty() && judgeMent == q.peek().time) {
                
                ++judgeMent ;
                for(int i=0; i<x; i++) {
                    for(int j=0; j<y; j++) {
                        if(pre_map[i][j]== -1) {
                            //레드
                            pre_map[i][j] = 4;
                        }
                        if(pre_map[i][j]== -2) {
                            //그린
                            pre_map[i][j] = 3;
                        }
                    }//end of for loop
                }//end of for loop
                
            }//end of if
        
            
            
        }//end of while loop
        
        //업데이트
        rearAns = Math.max(rearAns, flower);
    
        
        q = new LinkedList<>(); //마지막엔 큐를 초기화 
        for(int i=0; i<x; i++) { for(int j=0; j<y; j++) pre_map[i][j] = temp[i][j]; }
    }
    
    static void print(int[][] v) {
        for(int i=0; i<x; i++) {
            for(int j=0; j<y; j++) {
                System.out.print(v[i][j]+" ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) throws Exception{
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        x = Integer.parseInt(st.nextToken());
        y = Integer.parseInt(st.nextToken());
        G = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        
        map = new int[x][y];
        pre_map = new int[x][y];
        
        for(int i=0; i<x; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<y; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                pre_map[i][j] = map[i][j]; 
                if(map[i][j] == 2) {
                    al.add(new POS(i,j));
                }
            }//end of first loop
        }//end of second loop
        
        //배양액을 뿌릴 수 있는곳 개수 만큼 visit 배열 생성
        visit = new int[al.size()];
        
        //visit 으로 G, R를 뿌릴 위치를 찾는다. al.size() 만큼 
        cultureFluidGreen(0,0);
        System.out.println(rearAns);
    }
 
}
 

G, R 순열로 뽑아서 배양액을 뿌릴 수 있는곳에 뿌리고 ! 

BFS 탐색을 하면 된다.