[백준 JAVA] 18809번: Gaaaaaaaaaarden

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

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static int N, M, G, R, ans = 0, cnt = 0;
	public static int[] green, red, visited;
	public static int[][] map, copyMap;
	public static int[] dr = { -1, 0, 1, 0 };
	public static int[] dc = { 0, 1, 0, -1 };
	public static List<int[]> list = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		// 1. 입력받기
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		G = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		map = new int[N][M];
		copyMap = new int[N][M];
		green = new int[G]; // 초록색 배양액 위치
		red = new int[R]; // 빨간색 배양액 위치

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				// 배양액을 뿌릴 수 있는 땅 리스트에 저장
				if (map[i][j] == 2) {
					list.add(new int[] { i, j });
					cnt++;
				}
			}
		}
		
		visited = new int[cnt];

		// 2. 배양액 위치 설정
		// 2-1. 초록색 배양액 위치
		cGreen(0, 0);

		// 4. 출력하기
		System.out.println(ans);
	}

	public static void cGreen(int at, int depth) {
		if (depth == G) {
			// 2-1. 빨간색 배양액 위치
			cRed(0, 0);
			return;
		}

		for (int i = at; i < cnt; i++) {
			green[depth] = i;
			visited[i] = 1;
			cGreen(i + 1, depth + 1);
			visited[i] = 0;
		}
	}

	public static void cRed(int at, int depth) {
		if (depth == R) {
			// 3. 퍼트리기
			copy();
			pu();
			int tmp = 0;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (copyMap[i][j] == 3) {
						tmp++;
					}
				}
			}

			if (tmp > ans) {
				ans = tmp;
			}
			return;
		}

		for (int i = at; i < cnt; i++) {
			if (visited[i] == 0) {
				red[depth] = i;
				cRed(i + 1, depth + 1);
			}
		}
	}

	public static void pu() {
		// 3-1. 초록색, 빨간색 배양액 뿌리기
		Queue<int[]> gQ = new LinkedList<>();
		Queue<int[]> rQ = new LinkedList<>();
		int time = 0;
		for (int i = 0; i < G; i++) { // 초록색
			int idx = green[i];
			int[] cur = list.get(idx);
			gQ.offer(new int[] { cur[0], cur[1] });
			copyMap[cur[0]][cur[1]] = 0;
		}

		for (int i = 0; i < R; i++) { // 빨간색
			int idx = red[i];
			int[] cur = list.get(idx);
			rQ.offer(new int[] { cur[0], cur[1] });
			copyMap[cur[0]][cur[1]] = 0;
		}
		
		// 3-2. 1초에 한번씩 뿌리기
		while (!gQ.isEmpty() || !rQ.isEmpty()) {
			int gSize = gQ.size();
			int rSize = rQ.size();
			time++;

			for (int i = 0; i < gSize; i++) { // 초록색 퍼지기
				int[] cur = gQ.poll();
				
				if(copyMap[cur[0]][cur[1]] == 3) {
					continue;
				}

				for (int d = 0; d < 4; d++) {
					int nr = cur[0] + dr[d];
					int nc = cur[1] + dc[d];
					if (nr < 0 || nr >= N || nc < 0 || nc >= M)
						continue;
					int cv = copyMap[nr][nc];
					
					if (cv == 1 || cv == 2) {
						copyMap[nr][nc] = 4 * time;
						gQ.offer(new int[] { nr, nc });
					}
				}
			}

			for (int i = 0; i < rSize; i++) { // 빨간색 퍼지기
				int[] cur = rQ.poll();

				for (int d = 0; d < 4; d++) {
					int nr = cur[0] + dr[d];
					int nc = cur[1] + dc[d];
					if (nr < 0 || nr >= N || nc < 0 || nc >= M)
						continue;
					int cv = copyMap[nr][nc];
					
					if (cv == 4 * time) {
						copyMap[nr][nc] = 3;
						continue;
					}
					
					if (cv == 1 || cv == 2) {
						copyMap[nr][nc] = 0;
						rQ.offer(new int[] { nr, nc });
					}
				}
			}
		}
	}

	public static void copy() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				copyMap[i][j] = map[i][j];
			}
		}
	}
}