BOJ_Gaaaaaaaaaarden_18809

1. 과정

- 배양액을 뿌릴 땅을 선택하는 방법은 여러가지가 있지만 나는 배양액을 뿌릴 수 있는 땅 중에 getRedList라는 메소드로 빨간 배양액을 뿌릴 땅을 선택하고, getGreenList라는 메소드로 남은 땅 중에 초록 배양액을 뿌릴 땅을 선택하는 방식으로 했다.

- 혹은 순열로 배양액 수만큼 뽑은 다음에, 앞부분 부터 초록 배양액 개수만큼, 나머지는 빨간 배양액으로 설정해도 된다.

- 이제 배양액을 뿌릴 차례인데, Land라는 클래스를 만들어 좌표와 땅인지 호수인지 배양액인지 꽃인지를 나타내는 num변수와 완료상태를 나타내는 state변수가 있다.

- 먼저 배양액을 다 뿌리고 state를 완료상태인 1로 설정해준다.

- 그다음부터 bfs로 상하좌우 탐색하며 빈 땅의 경우 배양액을 뿌리고, 배양액이 뿌려져 있다면 꽃으로 만들어준다.

- 여기서 중요한 점은, 배양액을 뿌리고 queue에 넣는데, 한턴이 다 끝나고 나면 모두 상황 종료를 해 줘야한다.

 

 

2. 구현

언어 : JAVA

메모리 : 281,208 kb

시간 : 1,076 ms

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

public class BOJ_Gaaaaaaaaaarden_18809 {
	static int R, C, Green, Red, answer, availTotal;
	static Land[][] map;
	static boolean[] visit;
	static ArrayList<Land> avail = new ArrayList<>();
	static ArrayList<Integer> redList = new ArrayList<Integer>();
	static ArrayList<Integer> greenList = new ArrayList<Integer>();
	static int[] dr = { -1, 1, 0, 0 };
	static int[] dc = { 0, 0, -1, 1 };

	static class Land {
		int r, c, num, state;

		public Land(int r, int c, int num, int state) {
			this.r = r;
			this.c = c;
			this.num = num;
			this.state = state;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		R = Integer.parseInt(s[0]);
		C = Integer.parseInt(s[1]);
		Green = Integer.parseInt(s[2]);
		Red = Integer.parseInt(s[3]);
		answer = 0;
		map = new Land[R][C];
		avail.clear();
		// 0(호수), 1(배양액 뿌릴 수 없는 땅), 2(배양액 뿌릴 수 있는 땅), 3(red 배양액), 4(green 배양액), 5(꽃)
		for (int i = 0; i < R; ++i) {
			s = br.readLine().split(" ");
			for (int j = 0; j < C; ++j) {
				map[i][j] = new Land(i, j, Integer.parseInt(s[j]), 0);
				// 배양액 뿌릴 수 있는 땅 저장
				if (map[i][j].num == 2) {
					avail.add(map[i][j]);
				}
			}
		}
		// 배양액 뿌릴 수 있는 땅 개수
		availTotal = avail.size();
		visit = new boolean[availTotal];
		redList.clear();
		greenList.clear();
		getRedList(0);
		System.out.println(answer);
	}

	private static void getRedList(int n) {
		if (redList.size() == Red) {
			getGreenList(0);
			return;
		}

		for (int i = n; i < availTotal; ++i) {
			if (visit[i])
				continue;
			visit[i] = true;
			redList.add(i);
			getRedList(i + 1);
			visit[i] = false;
			redList.remove(redList.size() - 1);
		}
	}

	private static void getGreenList(int n) {
		if (greenList.size() == Green) {
			solve();
			return;
		}

		for (int i = n; i < availTotal; ++i) {
			if (visit[i])
				continue;
			visit[i] = true;
			greenList.add(i);
			getGreenList(i + 1);
			visit[i] = false;
			greenList.remove(greenList.size() - 1);
		}

	}

	private static void solve() {
		Land[][] tmap = getMap();
		Queue<Land> q = new LinkedList<>();
		for (int i = 0; i < redList.size(); ++i) {
			int n = redList.get(i);
			Land land = avail.get(n);
			// 빨간 배양액을 넣고, 상태는 완료상태
			tmap[land.r][land.c].num = 3;
			tmap[land.r][land.c].state = 1;
			q.add(tmap[land.r][land.c]);
		}
		for (int i = 0; i < greenList.size(); ++i) {
			int n = greenList.get(i);
			Land land = avail.get(n);
			// 초록 배양액을 넣고, 상태는 완료상태
			tmap[land.r][land.c].num = 4;
			tmap[land.r][land.c].state = 1;
			q.add(tmap[land.r][land.c]);
		}
		int flower = 0;
		while (!q.isEmpty()) {
			int qSize = q.size();
			for (int k = 0; k < qSize; ++k) {
				Land land = q.poll();
				int r = land.r;
				int c = land.c;
				int num = land.num;
				int tr, tc;
				for(int i=0; i<4; ++i) {
					tr = r+dr[i];
					tc = c+dc[i];
					// 범위 벗어나면 continue
					if(tr<0 || tc<0 || tr>=R || tc>=C) continue;
					// 호수이거나 상황 종료된 땅이면 continue
					if(tmap[tr][tc].num==0 || tmap[tr][tc].state==1) continue;
					// 꽃인곳도 못가지만 어차피 상황 종료이니 일단 패스~
					// 배양액 퍼뜨림
					// 배양액이 뿌려져 있지 않은 경우 그냥 뿌리면서 q에 넣음
					if(tmap[tr][tc].num==1||tmap[tr][tc].num==2) {
						tmap[tr][tc].num = num;
						q.add(tmap[tr][tc]);
					}
					// 배양액이 같은경우는 무시하고, 서로 다른 경우 꽃을 피움
					else if(num!=tmap[tr][tc].num) {
						tmap[tr][tc].num = 5;
						tmap[tr][tc].state = 1;
						flower++;
					}
				}
			}
			// 배양액을 뿌렸지만 꽃이 만들어지지 않은 배양액은 모두 상황 종료 시켜주고 다시 q에 넣음
			Queue<Land> tq = new LinkedList<>();
			qSize = q.size();
			for(int i=0; i<qSize; ++i) {
				Land land = q.poll();
				if(land.num==3||land.num==4) {
					land.state = 1;
					tq.add(land);
				}
			}
			q = tq;
		}
		answer = Math.max(answer, flower);
	}

	private static void print(Land[][] tmap) {
		System.out.println();
		for (int i = 0; i < R; ++i) {
			for (int j = 0; j < C; ++j) {
				System.out.print(tmap[i][j].num+" ");
			}System.out.println();
		}
	}

	private static Land[][] getMap() {
		Land[][] tmap = new Land[R][C];
		for (int i = 0; i < R; ++i) {
			for (int j = 0; j < C; ++j) {
				tmap[i][j] = new Land(i, j, map[i][j].num, 0);
			}
		}
		return tmap;
	}
}