BOJ 18809번 Gaaaaaaaaaarden 문제 자바(java) 풀이
문제정리
- 빨간색, 초록색 배양액을 이용해 꽃을 피운다.
- 배양액은 매 초마다 이전에 배양액이 도달한 적이 없는 인접한 땅으로 퍼져나간다.
- 초록색 배양액과 빨간색 배양액이 동일한 시간에 도달한 경우 땅에서 꽃이 핀다.
- 꽃이 핀 땅에서는 배양액이 사려저 더 이상 배양액이 퍼지지 않는다.
- 모든 배양액은 서로 다른 곳에 뿌린다.
- 꽃의 최대 개수를 구하여라
문제 풀이
배양액을 놓을 수 있는 위치가 여러군데 있습니다. 그 중에서 놓을 곳을 정해야 합니다.
또한 그 위치에 어떠한 색의 배양액을 놓을지 정해야합니다.
그래서 처음에 배양액을 놓을 곳의 순열을 구하고 배양액의 순열을 또 따로 구해서 하였습니다.
그렇게 하니 시간초과....
그래서 배양액의 위치를 따로 구하지 않고 index를 이용하여 초록색과 빨간색을 어디 놓을지 결정합니다.
조합 구하기
초록색과 빨간색의 배양액을 놓을 위치의 조합을 따로 구합니다.
- 먼저 초록색에 관해서 어디 놓을지 순열을 구합니다. 이때 visited 배열을 이용합니다.
- 그리고 빨간색도 똑같이 구합니다. visited로 방문했다면 초록색이 놓을 위치이므로 그건 제외하고 빨간색이 놓을 위치를 구합니다.
기본적인 순열을 구하는 방법과 같습니다. 다른점이라 하면 원래는 하나의 배열에 순서를 담았다 하면 그것을 reds와 greens 배열에 따로 숫자를 담아서 사용한다는 점입니다.
- 배양액의 개수만큼 숫자를 초록색 따로 빨간색 따로 뽑으면 그 위치에 그 색깔의 배양액을 놓으면 됩니다.
예를들어 배양액을 놓을 수 있는 곳이 5곳이고 초록색이 3개 빨간색이 2개라면
초록색 = [0,1,2], 빨간색 = [3,4] 처럼 놓을 위치가 정해지게 됩니다.
퍼트리기(bfs)
state 배열을 이용해서 원본 배열을 건드리지 않고 배양액이 퍼진 상태를 저장하며 퍼져나갑니다.
1. state 배열을 초기화 합니다
2. 순열을 통해 어디에 어떤 배양액을 놓을지 정하였습니다. 그것에 맞게 state 배열에 배양액을 놓습니다. 그리고 queue에 위치를 넣습니다.
RED는 3, GREEN은 4, 꽃은 5입니다.
3. queue에서 하나씩 꺼내며 4 방향으로 퍼트립니다.
3.0 꽃이 핀 자리라면 퍼지지 않습니다.
3.1 유효한 위치이고 호수가 아닌 경우 이동
4. 이동할때 다음과 같이 3가지 경우로 나뉩니다.
4.1 아직 배양액이 퍼지지 않은 상태 => 퍼트림
4.2 빨간색이 있을때 초록색이 퍼지는 경우 => 꽃, 퍼지지 않기 때문에 queue에 담지 않음
4.3 초록색이 있을때 빨간색이 퍼지는 경우 => 꽃, 퍼지지 않기 때문에 queue에 담지 않음
- 실행시간: 1060 ms
- 메모리: 280379 kb