[백준 / BOJ] 18809 Gaaaaaaaaaarden (Java)

문제

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

18809번: Gaaaaaaaaaarden

N*M크기의 정원에 빨간색 배양액 R개 초록색 배양액 G개를 뿌린다. 배양액을 뿌릴 수 있는 위치는 R+G곳 이며, 배양액을 뿌린 위치는 매 초마다 인접한 영역으로 퍼져나간다. 

서로 다른 색의 배양액이 동시에 만나면 꽃이 피며, 배양액은 사라진다. 이때, 피울 수 있는 최대 꽃의 개수를 구하는 문제다 

---

풀이

조합과 BFS로 풀리는 문제다.

문제에서 설명한 그대로 구현하면 되는데, 조합을 구현할때와 BFS를 구현할때, 주의할 점이 있었다.

 

1. 조합을 구현할때.

2가지 색을 R+G개의 땅에 뿌려주므로, 조합에 중복이 많이 생긴다. 예를들어, 1번 빨간색 배양액을 첫번째 지점에 뿌리고, 2번 빨간색 배양액을 두번째 지점에 뿌리는 것과 2번 빨간색 배양액을 첫번째 지점에 뿌리고, 1번 빨간색 배양액을 두번째 지점에 뿌리는것은 같은 경우의 수 이다. 따라서, 이 중복을 체크해주기 위해, Set을 사용해서, 이미 탐색한 조합이라면 제외했다.

 

소스코드

	private int combineDrop(int idx, int cosumedGreenDropCount, int cosumedRedDropCount, long combination){
		if(cosumedRedDropCount == this.redDropCount && cosumedGreenDropCount == this.greenDropCount){
			while(combination < this.maxCombination) combination *= 10;
			if(this.combinationCheck.contains(combination)) return 0;
			this.combinationCheck.add(combination);
			int flower = this.bloom(combination);
			return flower;
		}
		int ans = 0;
		for(int i = idx; i < this.positions.size(); i++){
			if(cosumedGreenDropCount < this.greenDropCount) 
				ans = Math.max(ans, this.combineDrop(i+1, cosumedGreenDropCount+1, cosumedRedDropCount, combination*10+1L));
			if(cosumedRedDropCount < this.redDropCount)
				ans = Math.max(ans, this.combineDrop(i+1, cosumedGreenDropCount, cosumedRedDropCount+1, combination*10+2L));
			combination *= 10;
		}
		return ans;
	}

효율성을 위해 배양액을 뿌린조합을 long으로 표현해줬다.

예를들어, 6개의 지점중에 빨간색 배양액을 2번 3번, 초록색 배양액을 5번 6번에 뿌렸다면 combination 파라미터는 022011이 된다.

 

2. 배양액을 뿌린후, BFS를 수행할때

3차원 체크배열을 사용해서, 각 색별로 방문여부를 체크해줬다.

check[색][y][x] = 방문 시간

이때, 반대되는 색이 이미 (y,x)지점을 지나갔을수도 있으므로, 반대되는색의 체크배열 현재위치가 0인지 체크해줘야한다. 또한, 하나의 지점에서 여러번 꽃 피는경우를 체크해줘야한다. (한 지점으로 여러 경로에서 진입하는 경우)

 

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/18809%20Gaaaaaaaaaarden/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃