[백준] 18809 Gaaaaaaaaaarden -JAVA // le_effort

Gaaaaaaaaaarden

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	1405	589	380	39.460%

문제

길고 길었던 겨울이 끝나고 BOJ 마을에도 봄이 찾아왔다. BOJ 마을에서는 꽃을 마을 소유의 정원에 피우려고 한다. 정원은 땅과 호수로 이루어져 있고 2차원 격자판 모양이다.

인건비 절감을 위해 BOJ 마을에서는 직접 사람이 씨앗을 심는 대신 초록색 배양액과 빨간색 배양액을 땅에 적절하게 뿌려서 꽃을 피울 것이다. 이 때 배양액을 뿌릴 수 있는 땅은 미리 정해져있다.

배양액은 매 초마다 이전에 배양액이 도달한 적이 없는 인접한 땅으로 퍼져간다.

아래는 초록색 배양액 2개를 뿌렸을 때의 예시이다. 하얀색 칸은 배양액을 뿌릴 수 없는 땅을, 황토색 칸은 배양액을 뿌릴 수 있는 땅을, 하늘색 칸은 호수를 의미한다.

초록색 배양액과 빨간색 배양액이 동일한 시간에 도달한 땅에서는 두 배양액이 합쳐져서 꽃이 피어난다. 꽃이 피어난 땅에서는 배양액이 사라지기 때문에 더 이상 인접한 땅으로 배양액을 퍼트리지 않는다.

아래는 초록색 배양액 2개와 빨간색 배양액 2개를 뿌렸을 때의 예시이다.

배양액은 봄이 지나면 사용할 수 없게 되므로 주어진 모든 배양액을 남김없이 사용해야 한다. 예를 들어 초록색 배양액 2개와 빨간색 배양액 2개가 주어졌는데 초록색 배양액 1개를 땅에 뿌리지 않고, 초록색 배양액 1개와 빨간색 배양액 2개만을 사용하는 것은 불가능하다.

또한 모든 배양액은 서로 다른 곳에 뿌려져야 한다.

정원과 두 배양액의 개수가 주어져있을 때 피울 수 있는 꽃의 최대 개수를 구해보자.

입력

첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두고 주어진다.

그 다음 N개의 줄에는 각 줄마다 정원의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0, 1, 2이다. 0은 호수, 1은 배양액을 뿌릴 수 없는 땅, 2는 배양액을 뿌릴 수 있는 땅을 의미한다.

배양액을 뿌릴 수 있는 땅의 수는 R+G개 이상이고 10개 이하이다.

출력

첫째 줄에 피울 수 있는 꽃의 최대 개수를 출력한다.

예제 입력 1 복사

xxxxxxxxxx
2 2 1 1
2 1
1 2

예제 출력 1 복사

xxxxxxxxxx
2

예제 입력 2 복사

xxxxxxxxxx
3 3 2 1
2 1 0
1 0 1
2 1 2

예제 출력 2 복사

xxxxxxxxxx
2

예제 입력 3 복사

xxxxxxxxxx
4 3 1 1
0 2 0
2 1 2
0 1 0
1 1 1

예제 출력 3 복사

xxxxxxxxxx
1

예제 입력 4 복사

xxxxxxxxxx
5 7 3 2
1 0 1 2 1 2 1
1 1 1 0 1 0 2
2 1 0 0 1 1 1
1 0 2 1 2 1 0
0 2 1 1 0 1 2

예제 출력 4 복사

xxxxxxxxxx
5

예제 입력 5 복사

xxxxxxxxxx
6 6 3 3
1 1 2 1 1 2
2 1 0 1 1 1
0 1 0 0 1 2
2 1 1 1 2 1
2 1 1 2 1 2
0 0 0 0 2 1

예제 출력 5 복사

xxxxxxxxxx
9

예제 입력 6 복사

xxxxxxxxxx
10 10 1 1
2 1 1 2 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1

예제 출력 6 복사

xxxxxxxxxx
0

예제 입력 7 복사

xxxxxxxxxx
13 20 2 5
1 1 0 1 0 0 1 0 0 2 0 1 0 0 1 2 0 2 1 1
1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1
0 0 0 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0
1 2 0 0 0 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0
0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1
1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0
0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0
0 1 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 1 0 0
0 0 2 0 0 0 0 0 2 1 0 1 0 0 0 0 0 0 0 0
1 1 0 0 0 1 0 2 1 0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 1 1 0 0 1 0 0 0 1 1 2 1 0 1 0 1
0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0

예제 출력 7 복사

xxxxxxxxxx
1

예제 입력 8 복사

xxxxxxxxxx
13 15 4 3
1 0 1 1 0 0 0 0 2 0 0 0 2 0 1
0 1 1 0 1 0 1 0 1 1 0 1 1 1 0
1 1 2 0 0 0 1 0 0 1 0 0 1 1 1
0 1 2 0 1 1 0 1 0 0 1 0 1 1 1
1 1 1 0 1 0 0 2 0 1 2 1 0 0 0
1 0 1 0 1 1 0 1 2 1 1 1 1 1 2
1 1 1 1 1 1 1 1 0 1 1 0 1 1 0
2 1 0 1 0 0 0 0 0 1 0 1 0 1 0
0 1 0 0 0 0 1 0 1 0 1 1 1 1 1
1 1 1 0 1 1 0 1 0 0 0 1 0 0 0
1 1 0 1 0 0 0 0 1 1 0 1 0 1 0
1 0 0 0 0 0 1 1 1 1 0 0 0 1 0
0 1 1 1 0 0 0 1 1 1 0 0 1 1 0

예제 출력 8 복사

xxxxxxxxxx
4

예제 입력 9 복사

xxxxxxxxxx
16 13 3 3
2 1 1 1 0 0 0 0 0 1 1 0 0
1 0 2 0 0 0 0 0 0 2 0 1 1
0 1 0 1 0 1 0 1 0 2 0 1 0
0 0 0 1 0 2 1 0 0 0 0 1 1
0 0 0 0 2 1 1 0 0 0 0 1 0
0 1 0 0 0 1 2 0 1 0 0 0 0
1 1 0 0 0 0 1 0 0 1 0 0 0
0 0 1 0 0 0 0 1 0 0 1 0 0
0 0 0 1 2 0 0 0 0 1 1 0 0
0 0 1 1 1 0 0 0 1 0 1 0 0
0 0 2 0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 0 1 1
0 0 0 0 0 0 1 0 0 1 1 0 0
0 0 0 1 1 0 1 2 0 1 0 0 1
1 1 0 0 1 0 0 1 0 0 0 0 1

예제 출력 9 복사

xxxxxxxxxx
2

예제 입력 10 복사

x
13 17 2 4
1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 0
1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1
1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 2 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1
1 1 1 1 1 1 1 2 1 1 1 1 1 1 0 1 1
1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 2 1 1 1 1 2 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1

 

 

 

풀이

사용 알고리즘 조합 + bfs

 

1. 초기 배양액을 놓을수 있는 위치를 따로 저장해준다

Node 클래스엔 x,y좌표만 들어있다

xxxxxxxxxx
​
        for(int i=1; i<=n; i++) {
            String[] tt = br.readLine().split(" ");
            for(int j=1; j<=m; j++) {
                map[i][j]= Integer.parseInt(tt[j-1]);
                if(map[i][j]==2) {
                    dfs_list.add(new Node(i,j));
                }
            }
        }

 

그 다음엔 초록,빨강의 초기배양액 위치를 조합 알고리즘으로 구해준다

나는 초록먼저 구하고 빨강색을 구했다.

 

public static void green_dfs(int level, int now) {
        if(level == g) {
            green.clear();
            for(int i=0; i<dfs_list.size(); i++) {
                if(dfs_visited[i]) {
                    Node a= dfs_list.get(i);
                    green.add(a);
                }
            }
            red_dfs(0,0);
            return ;
        }
        for(int i=now; i<dfs_list.size(); i++) {
            if(!dfs_visited[i]) {
                dfs_visited[i] = true;
                green_dfs(level+1,i+1);
                dfs_visited[i] = false;
            }
        }
    }

 

 

 

public static void red_dfs(int level, int now) {
        if(level == r) {
            red.clear();
            for(int i=0; i<dfs_list.size(); i++) {
                Node a = dfs_list.get(i);
                if(dfs_visited[i] && !green.contains(a)) {
                    red.add(a);
                }
            }
            bfs();
            return ;
        }
        for(int i=now; i<dfs_list.size(); i++) {
            if(!dfs_visited[i]) {
                dfs_visited[i] = true;
                red_dfs(level+1,i+1);
                dfs_visited[i]=false;
            }
        }
    }

초록에 이어 빨강까지 구했다면 bfs를 돌려준다

 

bfs도 똑같다

나는 초록을 먼저 돌리고 (시간체크) 빨강을 그 후에 돌려서

빨강과 초록의 시간이 같다면 꽃이 피므로 큐에 넣어주지 않았다

 

public static void bfs() {
        int flower =0;
        green_visited = new boolean[n+1][m+1];
        green_time = new int[n+1][m+1];
        red_visited = new boolean[n+1][m+1];
        red_time = new int[n+1][m+1];
        
        copy_map();
        Queue<Node>rq = new LinkedList<>();
        Queue<Node>gq = new LinkedList<>();
        
        for(int i=0; i<red.size(); i++) {
            rq.add(red.get(i));
            red_visited[red.get(i).x][red.get(i).y]=true;
        }
        for(int i=0; i<green.size(); i++) {
            green_visited[green.get(i).x][green.get(i).y]=true;
            gq.add(green.get(i));
        }
        
    
        while(!rq.isEmpty() && !gq.isEmpty()) {
            if(!gq.isEmpty()) {
                int rep = gq.size();
                while(rep-- !=0) {
                    Node a= gq.poll();          
                    green_visited[a.x][a.y] = true;
                    if(copy_map[a.x][a.y]==3) {
                        continue;
                    }
                    
                    for(int i=0; i<4; i++) {
                        int nx = a.x+dx[i];
                        int ny = a.y+dy[i];
                        if(isRange(nx,ny) && (copy_map[nx][ny]==1 || copy_map[nx][ny]==2) && !green_visited[nx][ny]) {
                            green_visited[nx][ny]=true;
                            green_time[nx][ny] = green_time[a.x][a.y]+1;
                            gq.add(new Node(nx,ny));
                        }
                    }
                }
            }
            if(!rq.isEmpty()) {
                int rep = rq.size();
                    while(rep-- !=0) {
                    Node a = rq.poll();
                    red_visited[a.x][a.y] = true;
        
                    if(copy_map[a.x][a.y]==3) {
                        continue;
                    }
                    for(int i=0; i<4; i++) {
                        int nx = a.x+dx[i];
                        int ny = a.y+dy[i];
                        if(isRange(nx,ny) && (copy_map[nx][ny]==1 || copy_map[nx][ny]==2) && !red_visited[nx][ny]) {
                            red_visited[nx][ny] = true;
                            red_time[nx][ny] = red_time[a.x][a.y]+1;
                            if(red_time[nx][ny]==green_time[nx][ny]) {
                                
                                flower++;
                                copy_map[nx][ny]=3;
                            }
                            else {
                                rq.add(new Node(nx,ny));
                            }
                        }
                    }
                }   
            }
            }
        ans = Math.max(ans, flower);

 

 

전체코드

import java.io.*;
import java.util.*;
​
public class Main {
    static int n,m,g,r;
    static int map[][];
    static boolean red_visited[][];
    static boolean green_visited[][];
    static int ans = 0;
    static boolean dfs_visited[];
    static int red_time[][];
    static int green_time[][];
    static int dx[] = {0,0,1,-1};
    static int dy[] = {1,-1,0,0};
    
    static int copy_map[][];
    static ArrayList<Node>dfs_list = new ArrayList<>();
    static ArrayList<Node>green = new ArrayList<>();
    static ArrayList<Node>red = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        m = Integer.parseInt(t[1]);
        g = Integer.parseInt(t[2]);
        r = Integer.parseInt(t[3]);
        
        map = new int[n+1][m+1];
        
        for(int i=1; i<=n; i++) {
            String[] tt = br.readLine().split(" ");
            for(int j=1; j<=m; j++) {
                map[i][j]= Integer.parseInt(tt[j-1]);
                if(map[i][j]==2) {
                    dfs_list.add(new Node(i,j));
                }
            }
        }
        dfs_visited = new boolean[dfs_list.size()];
        green_dfs(0,0);
        System.out.println(ans);
    }
    public static void copy_map() {
        copy_map = new int[n+1][m+1];
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                copy_map[i][j] = map[i][j];
            }
        }
    }
    public static void bfs() {
        int flower =0;
        green_visited = new boolean[n+1][m+1];
        green_time = new int[n+1][m+1];
        red_visited = new boolean[n+1][m+1];
        red_time = new int[n+1][m+1];
        
        copy_map();
        Queue<Node>rq = new LinkedList<>();
        Queue<Node>gq = new LinkedList<>();
        
        for(int i=0; i<red.size(); i++) {
            rq.add(red.get(i));
            red_visited[red.get(i).x][red.get(i).y]=true;
        }
        for(int i=0; i<green.size(); i++) {
            green_visited[green.get(i).x][green.get(i).y]=true;
            gq.add(green.get(i));
        }
        
    
        while(!rq.isEmpty() && !gq.isEmpty()) {
            if(!gq.isEmpty()) {
                int rep = gq.size();
                while(rep-- !=0) {
                    Node a= gq.poll();          
                    green_visited[a.x][a.y] = true;
                    if(copy_map[a.x][a.y]==3) {
                        continue;
                    }
                    
                    for(int i=0; i<4; i++) {
                        int nx = a.x+dx[i];
                        int ny = a.y+dy[i];
                        if(isRange(nx,ny) && (copy_map[nx][ny]==1 || copy_map[nx][ny]==2) && !green_visited[nx][ny]) {
                            green_visited[nx][ny]=true;
                            green_time[nx][ny] = green_time[a.x][a.y]+1;
                            gq.add(new Node(nx,ny));
                        }
                    }
                }
            }
            if(!rq.isEmpty()) {
                int rep = rq.size();
                    while(rep-- !=0) {
                    Node a = rq.poll();
                    red_visited[a.x][a.y] = true;
        
                    if(copy_map[a.x][a.y]==3) {
                        continue;
                    }
                    for(int i=0; i<4; i++) {
                        int nx = a.x+dx[i];
                        int ny = a.y+dy[i];
                        if(isRange(nx,ny) && (copy_map[nx][ny]==1 || copy_map[nx][ny]==2) && !red_visited[nx][ny]) {
                            red_visited[nx][ny] = true;
                            red_time[nx][ny] = red_time[a.x][a.y]+1;
                            if(red_time[nx][ny]==green_time[nx][ny]) {
                                
                                flower++;
                                copy_map[nx][ny]=3;
                            }
                            else {
                                rq.add(new Node(nx,ny));
                            }
                        }
                    }
                }   
            }
            }
        ans = Math.max(ans, flower);
    }
    public static void red_dfs(int level, int now) {
        if(level == r) {
            red.clear();
            for(int i=0; i<dfs_list.size(); i++) {
                Node a = dfs_list.get(i);
                if(dfs_visited[i] && !green.contains(a)) {
                    red.add(a);
                }
            }
            bfs();
            return ;
        }
        for(int i=now; i<dfs_list.size(); i++) {
            if(!dfs_visited[i]) {
                dfs_visited[i] = true;
                red_dfs(level+1,i+1);
                dfs_visited[i]=false;
            }
        }
    }
    public static void green_dfs(int level, int now) {
        if(level == g) {
            green.clear();
            for(int i=0; i<dfs_list.size(); i++) {
                if(dfs_visited[i]) {
                    Node a= dfs_list.get(i);
                    green.add(a);
                }
            }
            red_dfs(0,0);
            return ;
        }
        for(int i=now; i<dfs_list.size(); i++) {
            if(!dfs_visited[i]) {
                dfs_visited[i] = true;
                green_dfs(level+1,i+1);
                dfs_visited[i] = false;
            }
        }
    }
    
    public static boolean isRange(int x, int y) {
        if(x>=1 && y>=1 && x<=n && y<=m) {
            return true;
            
        }
        else {
            return false;
        }
    }   
}
​
class Node{
    int x,y;
    Node(int x, int y){
        this.x=x;
        this.y=y;
    }
}
​