[JAVA] 백준 (골드1) 18809번 Gaaaaaaaaaarden

링크

https://www.acmicpc.net/problem/18809

---

입력 예제

2 2 1 1
2 1
1 2

---

출력 예제

2

---

풀이

문제는 2단계로 구분해서 풀어야 한다. 일단 배양액을 뿌릴 수 있는 땅에 배양액을 모두 뿌리는 경우를 구하고, 각 경우에서 같은 시간에 다른 배양액이 도달할 경우 꽃의 개수를 구해야 한다.

우선 배양액을 뿌릴수 있는 땅을 List에 저장한다.

List<int[]> fertileLand = new ArrayList<>();

for (int i = 0; i < N; i++) {
    st = new StringTokenizer(br.readLine());
    for (int j = 0; j < M; j++) {
        garden[i][j] = Integer.parseInt(st.nextToken());
        if (garden[i][j] == 2) {
            fertileLand.add(new int[]{i, j});
        }
    }
}

백트래킹으로 배양액을 뿌릴수 있는 모든 경우에 대해 탐색하면서 각 배양액을 모두 사용하였을 때 가지치기를 한다. 그리고 이때 배양액을 뿌린 땅에 대해 BFS를 진행하여 꽃에 개수를 카운트한다.

static void dfs(int depth, int green, int red, int[] selected) {
    if (green == G && red == R) {
        maxFlowers = Math.max(maxFlowers, bfs(selected));
        return;
    }
    
    if (depth == fertileLand.size()) {
        return;
    }
    
    if (green < G) {  //초록색 배양액 사용
        selected[depth] = GREEN;
        dfs(depth + 1, green + 1, red, selected);
        selected[depth] = EMPTY;
    }
    
    if (red < R) {  //빨간색 배양액 사용
        selected[depth] = RED;
        dfs(depth + 1, green, red + 1, selected);
        selected[depth] = EMPTY;
    }
    
    dfs(depth + 1, green, red, selected);  //배양액을 사용하지 않음
}

BFS를 진행할 때는 방문 여부와 함께 최소 시간을 계산하여 동일한 시간에 배양액이 도달할 때를 확인해야 한다. 해당 좌표의 땅의 정보를 저장하기 위해 Land 클래스를 만들어 Queue에 저장한다. 우선 배양액을 뿌린 땅에 대해 모두 큐에 삽입한 뒤 탐색을 진행한다.

static int bfs(int[] selected) {
    int[][] time = new int[N][M];
    char[][] visited = new char[N][M];
    Queue<Land> queue = new LinkedList<>();
    
    //배양액이 뿌리진 땅을 큐에 추가
    for (int i = 0; i < fertileLandSize; i++) {
        if (selected[i] > EMPTY) {
            int[] cur = fertileLand.get(i);
            int r = cur[0];
            int c = cur[1];
            visited[r][c] = (selected[i] == GREEN) ? 'G' : 'R';
            queue.add(new Land(r, c, selected[i], 0));
        }
    }
    
    int flowers = 0;
    while (!queue.isEmpty()) {
        Land cur = queue.poll();
        int r = cur.row;
        int c = cur.col;
        int type = cur.type;
        int t = cur.time;
        
        if (visited[r][c] == 'F') {  //이미 꽃이면 스킵
            continue;
        }
        
        for (int i = 0; i < 4; i++) {
            int nextR = r + dr[i];
            int nextC = c + dc[i];
            
            if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= M) {
                continue;
            }
            
            if (garden[nextR][nextC] == 0 || visited[nextR][nextC] == 'F') {
                continue;
            }
            
            if (visited[nextR][nextC] == EMPTY) {  //방문하지 않은 경우
                visited[nextR][nextC] = (type == GREEN) ? 'G' : 'R';
                time[nextR][nextC] = t + 1;
                queue.add(new Land(nextR, nextC, type, t + 1));
            } else if (visited[nextR][nextC] == 'G' && type == RED && time[nextR][nextC] == t + 1) {
                visited[nextR][nextC] = 'F';
                flowers++;
            } else if (visited[nextR][nextC] == 'R' && type == GREEN && time[nextR][nextC] == t + 1) {
                visited[nextR][nextC] = 'F';
                flowers++;
            }
        }
    }
    return flowers;
}

static class Land{
    int row;
    int col;
    int type;
    int time;
    
    public Land(int row, int col, int type, int time) {
        this.row = row;
        this.col = col;
        this.type = type;
        this.time = time;
    }
}

전체 코드

//백준
public class Main {

    static final int EMPTY = 0;
    static final int GREEN = 1;
    static final int RED = 2;

    static int[][] garden;
    static int N, M, G, R;
    static List<int[]> fertileLand = new ArrayList<>();
    static int fertileLandSize;
    static int maxFlowers = 0;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        G = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());

        garden = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                garden[i][j] = Integer.parseInt(st.nextToken());
                if (garden[i][j] == 2) {
                    fertileLand.add(new int[]{i, j});
                }
            }
        }

        fertileLandSize = fertileLand.size();
        dfs(0, 0, 0, new int[fertileLandSize]);
        System.out.println(maxFlowers);
    }

    static void dfs(int depth, int green, int red, int[] selected) {
        if (green == G && red == R) {
            maxFlowers = Math.max(maxFlowers, bfs(selected));
            return;
        }

        if (depth == fertileLand.size()) {
            return;
        }

        if (green < G) {  //초록색 배양액 사용
            selected[depth] = GREEN;
            dfs(depth + 1, green + 1, red, selected);
            selected[depth] = EMPTY;
        }

        if (red < R) {  //빨간색 배양액 사용
            selected[depth] = RED;
            dfs(depth + 1, green, red + 1, selected);
            selected[depth] = EMPTY;
        }

        dfs(depth + 1, green, red, selected);  //배양액을 사용하지 않음
    }

    static int bfs(int[] selected) {
        int[][] time = new int[N][M];
        char[][] visited = new char[N][M];
        Queue<Land> queue = new LinkedList<>();

        //배양액이 뿌리진 땅을 큐에 추가
        for (int i = 0; i < fertileLandSize; i++) {
            if (selected[i] > EMPTY) {
                int[] cur = fertileLand.get(i);
                int r = cur[0];
                int c = cur[1];
                visited[r][c] = (selected[i] == GREEN) ? 'G' : 'R';
                queue.add(new Land(r, c, selected[i], 0));
            }
        }

        int flowers = 0;

        while (!queue.isEmpty()) {
            Land cur = queue.poll();
            int r = cur.row;
            int c = cur.col;
            int type = cur.type;
            int t = cur.time;

            if (visited[r][c] == 'F') {  //이미 꽃이면 스킵
                continue;
            }

            for (int i = 0; i < 4; i++) {
                int nextR = r + dr[i];
                int nextC = c + dc[i];

                if (nextR < 0 || nextR >= N || nextC < 0 || nextC >= M) {
                    continue;
                }

                if (garden[nextR][nextC] == 0 || visited[nextR][nextC] == 'F') {
                    continue;
                }

                if (visited[nextR][nextC] == EMPTY) {  //방문하지 않은 경우
                    visited[nextR][nextC] = (type == GREEN) ? 'G' : 'R';
                    time[nextR][nextC] = t + 1;
                    queue.add(new Land(nextR, nextC, type, t + 1));
                } else if (visited[nextR][nextC] == 'G' && type == RED && time[nextR][nextC] == t + 1) {
                    visited[nextR][nextC] = 'F';
                    flowers++;
                } else if (visited[nextR][nextC] == 'R' && type == GREEN && time[nextR][nextC] == t + 1) {
                    visited[nextR][nextC] = 'F';
                    flowers++;
                }
            }
        }

        return flowers;
    }

    static class Land{
        int row;
        int col;
        int type;
        int time;

        public Land(int row, int col, int type, int time) {
            this.row = row;
            this.col = col;
            this.type = type;
            this.time = time;
        }
    }
}