백준 18809번: Gaaaaaaaaaarden (JAVA)

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

18809번: Gaaaaaaaaaarden

문제

길고 길었던 겨울이 끝나고 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. 배양액 뿌리기 2. 뿌린 배양액이 퍼져나가기로 나눌 수 있다.

 

1. 배양액 뿌리기

• 배양액을 뿌릴 수 있는 위치를 canGrow라는 int 배열에 저장하였으며, 위치의 개수를 K에 저장하였다.
• 위치마다 R을 뿌릴지, G를 뿌릴지 결정하는데, 이는 1개 조합 만드는 경우 코드를 그냥 일렬로 두 번 쓰면 된다.
• R을 뿌렸다면 그 위치를 int 배열 reds에, G를 뿌렸다면 그 위치를 int 배열 greens에 저장한다.
• (경우의 수는 K! / (R!*G!*(K-R-G)!) 이며, 최대 1050(K=10, R=G=3)가지이다.)
• 선택을 너무 적게하여, 남은 모든 자리에 배양액을 뿌려도 모든 배양액을 못 뿌리는 경우는 조건을 통해 없애주었다.

 

2. 뿌린 배양액이 퍼져나가기

• 배양액의 위치를 queue에 저장하여 bfs를 돌린다.
• 이번에 퍼진 배양액끼리 만나야만 꽃이 되기에, 이번에 퍼진 배양액과 이전에 퍼진 배양액을 구분해야한다.
  • 나는 '꽃: 5, G:3, R:4, 안 마른 G:-3, 안마른 R:-4'로 설정하였다.
• 해당 칸이 -3or-4이고 -(기존 색상)이 -7이 되면 현재 퍼지는 배양액끼리 만났다는 뜻이다: 해당 위치에는 꽃이 핀다.
• bfs를 돌면서, 모든 칸에서 인접한 한 칸씩 배양액이 퍼졌다면, 다음 확산에서는 이번에 퍼진 배양액은 이전 배양액으로 바꾸어줘야한다. 또한, queue에서 뽑아낸 위치에 꽃이 있다면 bfs내 인접 칸을 찾는 과정을 스킵해야 한다.
  • 이 처리가 가장 까다로운 부분이라고 생각한다: 나는 bfs 내에서 퍼지는 과정을 '배양액이 마름' -> '1칸 퍼짐'으로 나누었다.

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static int M, N, G, R, K, ans, tempAns;
    static int[][] gaarden, tempGaarden;
    static int[] canGrow, reds, greens;
    static int[] choice;
    static boolean[][] visited;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {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());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        G = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        greens = new int[G];
        reds = new int[R];
        gaarden = new int[M][N];

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

        canGrow = new int[K];
        int idx = 0;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (gaarden[i][j] == 2) canGrow[idx++] = N*i + j;
            }
        }

        dfs(0, 0, 0);
        System.out.println(ans);
    }

	// 1. 가능한 조합 찾기
    static void dfs(int redCnt, int greenCnt, int start) {
        if (R+G-redCnt-greenCnt > K - start) {
            return;
        }

        if (redCnt + greenCnt == R+G) {
            tempAns = 0;
            tempGaarden = copy();

            // 꽃: 5, G:3, R:4, 안 마른 G:-3, 안마른 R:-4
            for (int i = 0; i < G; i++) {
                tempGaarden[greens[i]/N][greens[i]%N] = 3;
            }
            for (int i = 0; i < R; i++) {
                tempGaarden[reds[i]/N][reds[i]%N] = 4;
            }
            visited = new boolean[M][N];
            bfs();
        }

        if (redCnt < R) {
            for (int i = start; i < K; i++) {
                reds[redCnt] = canGrow[i];
                dfs(redCnt+1, greenCnt, i+1);
            }
        }

        if (greenCnt < G) {
            for (int i = start; i < K; i++) {
                greens[greenCnt] = canGrow[i];
                dfs(redCnt, greenCnt+1, i+1);
            }
        }
    }


    static int[][] copy(){
        int[][] tempGaarden = new int[M][N];
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                tempGaarden[i][j] = gaarden[i][j]; 
            }
        }
        return tempGaarden;
    }

	// 2. 배양액이 확산되면서 꽃을 만든다.
    static void bfs() {
        Queue<int[]> queue = new ArrayDeque<>();
        // 이전 배양액 말리기
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j] && (tempGaarden[i][j] == 3 || tempGaarden[i][j] == 4)) {
                    visited[i][j] = true;
                    queue.offer(new int[] {i, j, tempGaarden[i][j]});
                }
            }
        }
		
        // 배양액 확산
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int[] temp = queue.poll();
                int r = temp[0], c = temp[1], color = temp[2];
                if (tempGaarden[r][c] == 5) continue;
                tempGaarden[r][c] = color;
                visited[r][c] = true;
                queue.offer(new int[] {r, c, color});
            }
            size = queue.size();
            while (size-- > 0) {
                int[] temp = queue.poll();
                int r = temp[0], c = temp[1], color = temp[2];
                for (int dir = 0; dir < 4; dir++) {
                    int nr = r + dr[dir], nc = c + dc[dir];
                    if (nr < 0 || nr >= M || nc < 0 || nc >= N) continue;
                    if (visited[nr][nc]) continue;
                    if (tempGaarden[nr][nc] == 0 || tempGaarden[nr][nc] >= 3) continue;

                    if (tempGaarden[nr][nc] == 1 || tempGaarden[nr][nc] == 2) {
                        tempGaarden[nr][nc] = -tempGaarden[r][c];
                        queue.offer(new int[] {nr, nc, color});
                    } else if (tempGaarden[nr][nc] - tempGaarden[r][c] == -7) {
                        tempGaarden[nr][nc] = 5;
                        tempAns++;
                    }
                }
            }			
        }
        ans = Math.max(ans, tempAns);		
    }
}