https://www.acmicpc.net/problem/18809
18809번: Gaaaaaaaaaarden
첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두
www.acmicpc.net
코드설명
구현(implementation) + 시뮬레이션(Simulation) + DFS를 활용한 브루트푸스, 조합, 순열(BruteForce, Combination, Permutation, 깊이우선탐색) + BFS(너비우선탐색) + 시간초과(timeout) 를 활용하는 문제입니다.
처음에 구현했던 방법은 다음과 같습니다.
1. 사용할 배양지를 먼저 조합으로 구합니다.
2. 사용할 배양지 초록용액과 빨간용액의 순서를 순열로 넣습니다.
3. BFS탐색하여 꽃이 가장 많이피는 경우를 구합니다.
위의 방법을 통해 진행할경우 시간초과가 납니다.
이유는, 테스트케이스를 확인해보면, 순열을 구하고, 조합을 구하는 과정을 하기때문입니다.
최대크기 TC : https://www.acmicpc.net/board/view/88389 참고.
입력값
4 3 1 1
0 2 0
2 1 2
0 1 0
1 1 1
출력값
===============
0 10 0
10 1 2
0 1 0
1 1 1
---selectedComb---
0 1 20
1 0 30
---selectedComb---
0 1 30
1 0 20
===============
0 10 0
2 1 10
0 1 0
1 1 1
---selectedComb---
0 1 20
1 2 30
---selectedComb---
0 1 30
1 2 20
===============
0 2 0
10 1 10
0 1 0
1 1 1
---selectedComb---
1 0 20
1 2 30
---selectedComb---
1 0 30
1 2 20
입력값
3 3 2 1
2 1 0
1 0 1
2 1 2
===============
10 1 0
1 0 1
10 1 10
---selectedComb---
0 0 20
2 0 20
2 2 30
---selectedComb---
0 0 20
2 0 30
2 2 20
---selectedComb---
0 0 20
2 0 20
2 2 30
---selectedComb---
0 0 20
2 0 30
2 2 20
---selectedComb---
0 0 30
2 0 20
2 2 20
---selectedComb---
0 0 30
2 0 20
2 2 20
해결방안으로는, 배양지를 선택하면서 용액을 함께 넣어줍니다.
모든 for문을 다 돌지 않고도, "2" 배양지를 만날떄마다 3개의 선택지로 총 10번의 Level이 주어졌다고 볼 수 있으므로 최악
의 경우 3^10 정도의 경우의 수가 나올 것으로 보입니다.
문제 로직을 다시 정리해보면,
- 주어진 조건에 따라 초록색(G)과 빨간색(R) 배양액을 조합으로 선택하여 꽃이 피는 경우를 탐색합니다.
- DFS를 사용하여 가능한 배양액 조합을 선택하고, 이때 선택된 조합에 따라 map 배열을 업데이트합니다.
- 선택된 배양액 조합에 대해 BFS를 사용하여 배양액이 퍼져가는 과정을 시뮬레이션합니다. 이때, 초록색은 양수로, 빨간색은 음수로 visited 배열을 관리합니다.
- BFS를 통해 피어난 꽃의 개수를 계산하고, 최대 꽃 개수를 업데이트합니다.
- 최종적으로 구해진 최대 꽃 개수를 출력합니다.
또 문제에서 유의해야할점은 다음과 같습니다.
1. 저는 FLOWER_NUM = Integer.MAX_VALUE가 아닌 40 으로 선택했었기에 오류가 있었습니다.
꽃일경우 visited[][]에 40을 넣었었는데 최대값이 50 x 50 이므로 최악의 경우 2601 까지 올라갑니다. 그렇기에 40인 cnt가 저절로 세지면서 올바른 값이 안나왔었습니다...
2. 꽃의 위치를 고려할시 다음꽃의 위치만 고려하는 것이 아닌, 현재 위치에서도 고려해야합니다.
이유는, 먼저 들어간 꽃은 현재 위치가 꽃으로 변한것을 인식하지 못하기에 현재 위치또한 고려해줍니다.
현재 위치에서 꽃일경우 중단.
while(!q.isEmpty()) {
Node temp = q.poll();
if(visited[temp.r][temp.c]== FLOWER_NUM) { //이미 먼저 들어온 Queue도 꽃이라면 못움직이게 합니다.
continue;
}다음꽃일경우 중단.
if(visited[nr][nc] == FLOWER_NUM) continue;
또한 시간초과를 줄이기 위해서는 BFS에서 반복문의 순서 또한 중요합니다.
아래와 같이 처리할경우 너무 많은 경우를 반복문으로 검사하므로 시간초과가 발생합니다.
//만약 이동할곳이 빨간색이라면, time[][] 배열을 통해 같은 시간대라면 합쳐주고, 같은 시간대가 아니라면 continue 시킵니다.
else if(garden[nr][nc].kind == RED && temp.kind == GREEN) {
//이 경우에는 따로 큐에 안넣어도 됩니다.
if(garden[nr][nc].time == temp.time + 1) {
garden[nr][nc].kind = ALREADYFLOWERED;
garden[nr][nc].time = temp.time + 1;
alreadyFloweredCnt += 1;
}
}
//만약 이동할 곳에 이미 RED가 존재하는데 time마저 같다면, 합쳐줄 것 입니다.
else if(garden[nr][nc].kind == GREEN && temp.kind == RED) {
//이 경우에는 따로 큐에 안넣어도 됩니다.
if(garden[nr][nc].time == temp.time + 1) {
garden[nr][nc].kind = ALREADYFLOWERED;
garden[nr][nc].time = temp.time + 1;
alreadyFloweredCnt += 1;
}
}
//색이 안차있는 경우 넘겨줍니다.
else if( (garden[nr][nc].kind == GREEN && temp.kind == GREEN)|| (garden[nr][nc].kind == RED && temp.kind == RED)){
garden[nr][nc].time = temp.time + 1;
garden[nr][nc].kind = temp.kind;
q.offer(new Flower(nr, nc, temp.kind, temp.time + 1));
}
//색이 안차있는 경우 넘겨줍니다.
else {
garden[nr][nc].time = temp.time + 1;
garden[nr][nc].kind = temp.kind;
q.offer(new Flower(nr, nc, temp.kind, temp.time + 1));
}
}
반면에 아래와 같이 처리할경우 훨씬 빠릅니다.
차이점은,
예상되는 원인으로는
- 조건문의 순서: 두번째 코드에서는 temp.kind == GREEN 조건을 먼저 체크하고, 그 안에서 garden[nr][nc].kind에 대한 여러 조건을 확인합니다. 반면에 위의 코드에서는 garden[nr][nc].kind와 temp.kind의 여러 조건을 먼저 확인하고, 마지막에 else로써 처리합니다. 첫번째 코드는 더 빠른 종료 조건을 가지고 있어 효율적일 수 있습니다.
또한, 아래 코드는 사실상 배양액을 뿌릴 수있는 땅은 10개 미만이기에 50x50개의 가든이 주어졌다고 했을떄 꽃이 피는 경우를 먼저 조사하는 것보다 비어있는 칸을 먼저 조사하는것이 더 빠르기에라고 추측합니다.
if(temp.kind == GREEN) {
if(garden[nr][nc].kind == 0) {
garden[nr][nc].time = temp.time + 1;
garden[nr][nc].kind = GREEN;
q.offer(new Flower(nr, nc, temp.kind, temp.time + 1));
}
else if(garden[nr][nc].kind == GREEN) {
}
else if(garden[nr][nc].kind == RED) {
if(garden[nr][nc].time == temp.time + 1) {
garden[nr][nc].kind = ALREADYFLOWERED;
alreadyFloweredCnt += 1;
}
}
}
else if(temp.kind == RED) {
if(garden[nr][nc].kind == 0) {
garden[nr][nc].time = temp.time + 1;
garden[nr][nc].kind = RED;
q.offer(new Flower(nr, nc, temp.kind, temp.time + 1));
}
else if(garden[nr][nc].kind == RED) {
}
else if(garden[nr][nc].kind == GREEN) {
if(garden[nr][nc].time == temp.time + 1) {
garden[nr][nc].kind = ALREADYFLOWERED;
alreadyFloweredCnt += 1;
}
}
}
코드
시간초과 해결 한 코드입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M, K, G, R;
public static int[][] map;
public static int answer = 0;
public static int[] dx = {-1,1,0,0};
public static int[] dy = {0,0,-1,1};
public static Node[] selectedComb;
public static boolean[] greenRedVisited;
public static int[][] visited;
public static int GREEN_NUM = 20, RED_NUM = 30, FLOWER_NUM = Integer.MAX_VALUE; //처음에 FLOWER_NUM을 40 으로해서 visited가 시간별로 양수로 40으로 채워진 칸도 세서 오류가 났었습니다..
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
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];
selectedComb = new Node[G + R];
for(int i=0;i<G+R;i++) {
selectedComb[i] = new Node(0, 0, 0, 1);
}
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()); // 0 : 호수, 1 : 배양액X 2 : 배양액가능.
}
}
//1. 초록색 배양액과 빨간색 배양액의 개수만큼 땅을 조합으로 선택하고, 선택된 조합( (1,1), (2,3) (4,5) )가 선택되었다고 했을때 배양액이 G : 1 R : 2 개 있으면, GGR, GRG, RGG 이렇게 나타내기 위해 순열을 선택한다.
selectREDGREEN(0, 0, 0, 0, 0);
System.out.println(answer);
}
public static void selectREDGREEN(int level, int r, int c, int greenCnt, int redCnt) {
if(level == G + R) {
if(greenCnt == G && redCnt == R) {
answer = Math.max(answer, BFS());
}
return ;
}
if( c >= M) {
r = r + 1;
c = 0;
}
if( r >= N) return ;
// if(map[r][c] == 0 || map[r][c] == 1) { //0과 1일떄만 이아닌, 0, 1, 2, 일때 모두 작동시켜야 2일떄도 넘어가서 올바르게 DFS탐색가능하다.
selectREDGREEN(level, r, c + 1, greenCnt, redCnt);
// }
if(map[r][c] == 2) {
//초록색 선택하는경우.
selectedComb[level] = new Node(r, c, GREEN_NUM, 1);
map[r][c] = GREEN_NUM;
selectREDGREEN(level + 1, r, c + 1, greenCnt + 1, redCnt);
map[r][c] = 2;
//빨간색 선택하는 경우
selectedComb[level] = new Node(r, c, RED_NUM, 1);
map[r][c] = RED_NUM;
selectREDGREEN(level + 1, r, c + 1, greenCnt, redCnt + 1);
map[r][c] = 2;
}
}
public static int BFS() {
Queue<Node> q = new LinkedList<>();
visited = new int[N][M];
for(int i=0;i<selectedComb.length;i++) {
q.offer(selectedComb[i]);
if(selectedComb[i].type == GREEN_NUM) {
visited[selectedComb[i].r][selectedComb[i].c] = 1;
}else if(selectedComb[i].type == RED_NUM) {
visited[selectedComb[i].r][selectedComb[i].c] = -1;
}
}
//visited[][] 값에 초록색이라면 양수 +cnt, 빨간색이라면 음수 -cnt로 진행했는데.
//map
while(!q.isEmpty()) {
Node temp = q.poll();
if(visited[temp.r][temp.c]== FLOWER_NUM) { //이미 먼저 들어온 Queue도 꽃이라면 못움직이게 합니다.
continue;
}
for(int dir = 0; dir < 4; dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if(map[nr][nc] == 0) continue; //만약 호수인경우.
if(visited[nr][nc] == FLOWER_NUM) continue;
//만약 초록용액이라면,
if(temp.type == GREEN_NUM) {
//아무것도 없을시에는 바로 이동.
if(visited[nr][nc] == 0) {
visited[nr][nc] = temp.cnt + 1;
q.offer(new Node(nr, nc, temp.type, temp.cnt + 1));
}
else if(visited[nr][nc] > 0) {
// continue;
}
else if(visited[nr][nc] < 0) {
if(visited[nr][nc] + ( temp.cnt + 1 )== 0) {
visited[nr][nc] = FLOWER_NUM; //꽃이피면 q에 넣지않는다.
}
}
}
//만약 빨간용액이라면,
else if(temp.type == RED_NUM) {
//아무것도 없을시에는 바로 이동.
if(visited[nr][nc] == 0) {
visited[nr][nc] = -(temp.cnt + 1);
q.offer(new Node(nr, nc, temp.type, temp.cnt + 1));
}
else if(visited[nr][nc] < 0) {
// continue;
}
else if(visited[nr][nc] > 0) {
if(visited[nr][nc] - (temp.cnt + 1) == 0) {
visited[nr][nc] = FLOWER_NUM; //꽃이피면 q에 넣지않는다.
}
}
}
}
}
int flowerResult = 0;
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
if(visited[i][j] == FLOWER_NUM) {
flowerResult += 1;
}
}
}
return flowerResult;
}
}
class Node{
int r;
int c;
int type; //20 : 초록색, 30 : 빨간색
int cnt;
public Node(int r, int c, int type) {
this.r = r;
this.c = c;
this.type = type;
}
public Node(int r, int c, int type, int cnt) {
this.r = r;
this.c = c;
this.type = type;
this.cnt = cnt;
}
}
시간초과 해결 코드
조건문을 명확하게 해결하니 해결되었습니다.
비교할 Queue가 RED인 경우와, 비교할 Queue가 GREEN 인경우로 나누어서
- 다음 칸이 빈칸인경우
- 다음 칸이 RED인경우
- 다음 칸이 GREEN 인경우
- (다음 칸이 이미 꽃이핀 상태일경우, 이건 이미 앞에서 처리)
이렇게 명시적으로 처리하면 훨씬 빠릅니다.
만약, 이렇게 하지 않고 복잡한 조건으로 처리한다면 어떻게 될까? 시간초과가 난다. 해당 시간초과 코드는 이 코드 바로 아래에 있습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M, G, R;
public static int[][] map;
public static int answer = 0;
public static int GREEN = 2601, RED = 2602, ALREADYFLOWERED = 2603;
public static Flower[] selectedComb;
public static ArrayList<int[]> flowerableList = new ArrayList<>();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
G = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
// 0 : 호수 1 : (배양액을 뿌릴 수 없는 땅) 2 : 배양액을 뿌릴 수 있는 땅
map = new int[N][M];
selectedComb = new Flower[G+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) {
flowerableList.add(new int[] {i, j});
}
}
}
simulate(0, 0, 0, 0);
System.out.println(answer);
}
public static void simulate(int level, int selectedIndex, int green, int red) {
//만약 배양액을 모두 뿌렸다면 해당 Map에서 피울 수 있는 꽃의 최대 개수를 구할 것 입니다.
if(green == G && red == R) {
getFlowerSimulate();
return ;
}
if(selectedIndex >= flowerableList.size() || level >= G+R) {
return ;
}
int row = flowerableList.get(selectedIndex)[0];
int col = flowerableList.get(selectedIndex)[1];
//만약 배양액을 뿌릴 수 있는 땅이라면,
if(map[row][col] == 2) {
//아직 초록색 배양액을 뿌릴 수 있다면,
if(green < G) {
selectedComb[level] = new Flower(row, col, GREEN, 0);
map[row][col] = GREEN;
simulate(level + 1, selectedIndex + 1, green + 1, red);
map[row][col] = 2;
}
//아직 빨간색 배양액을 뿌릴 수 있다면,
if(red < R) {
selectedComb[level] = new Flower(row, col, RED, 0);
map[row][col] = RED;
simulate(level + 1, selectedIndex + 1, green, red + 1);
map[row][col] = 2;
}
}
//아무것도 뿌리지 않고 지나가는 경우도 있을 것 입니다.
simulate(level, selectedIndex + 1 , green, red);
}
public static void getFlowerSimulate() {
// System.out.println("=======new BEGIN==========");
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
Flower[][] garden = new Flower[N][M];
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
garden[i][j] = new Flower();
garden[i][j].time = Integer.MAX_VALUE;
garden[i][j].kind = 0;
}
}
Queue<Flower> q = new LinkedList<>();
//빨간색 배양액과 초록색 배양액을 하나의 큐에 넣어준다.
//이떄 큐에 빨간색인지, 초록색인지 구분하는 변수도 추가해준다.
for(int i=0;i<G+R;i++) {
q.offer(new Flower(selectedComb[i].r, selectedComb[i].c, selectedComb[i].kind, selectedComb[i].time));
garden[selectedComb[i].r][selectedComb[i].c].time = 0;
garden[selectedComb[i].r][selectedComb[i].c].kind = selectedComb[i].kind;
}
int alreadyFloweredCnt = 0;
while(!q.isEmpty()) {
Flower temp = q.poll();
//만약 해당 큐가 시작하려고하는데 이미 꽃이 핀 곳이었다면, 큐가 작동하지 않게 합니다.
if(garden[temp.r][temp.c].kind == ALREADYFLOWERED) {
continue;
}
for(int dir = 0; dir < 4; dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
//만약 범위를 벗어나면 큐가 작동하지 않습니다.
if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
//만약 호수라면 큐가 작동하지 않습니다.
if(map[nr][nc] == 0) continue;
if(garden[nr][nc].time <= temp.time) continue; // 만약 현재 시간과 같을경우에도 이동하지 못하게 처리해야한다. 그렇지 않으면 무한반복이 걸린다.
//만약 이미 합쳐진 곳이라면 큐가 작동하지 않습니다.
if(garden[nr][nc].kind == ALREADYFLOWERED) continue;
if(temp.kind == GREEN) {
if(garden[nr][nc].kind == 0) {
garden[nr][nc].time = temp.time + 1;
garden[nr][nc].kind = GREEN;
q.offer(new Flower(nr, nc, temp.kind, temp.time + 1));
}
else if(garden[nr][nc].kind == GREEN) {
}
else if(garden[nr][nc].kind == RED) {
if(garden[nr][nc].time == temp.time + 1) {
garden[nr][nc].kind = ALREADYFLOWERED;
alreadyFloweredCnt += 1;
}
}
}
else if(temp.kind == RED) {
if(garden[nr][nc].kind == 0) {
garden[nr][nc].time = temp.time + 1;
garden[nr][nc].kind = RED;
q.offer(new Flower(nr, nc, temp.kind, temp.time + 1));
}
else if(garden[nr][nc].kind == RED) {
}
else if(garden[nr][nc].kind == GREEN) {
if(garden[nr][nc].time == temp.time + 1) {
garden[nr][nc].kind = ALREADYFLOWERED;
alreadyFloweredCnt += 1;
}
}
}
}
answer = Math.max(answer, alreadyFloweredCnt);
}
}
}
class Flower{
int r;
int c;
int kind;
int time;
public Flower(int r, int c, int kind, int time) {
this.r=r;
this.c=c;
this.kind = kind;
this.time = time;
}
public Flower() {
}
}
시간초과가 납니다.
아래의 코드의 조건문같은경우, 비교연산이 매우 많이 이루어지고, 복잡합니다. 불필요한 비교연산이 너무 많이 이루어져서 시간초과가 발생하는 것으로 생각됩니다.
- else if( (garden[nr][nc].kind == GREEN && temp.kind == GREEN)|| (garden[nr][nc].kind == RED && temp.kind == RED)){: 이 부분은 두 가지 경우를 처리하는데, 현재 위치의 꽃이 없거나(temp.kind가 GREEN 또는 RED) 이동하려는 꽃과 같은 색(temp.kind)인 경우를 의미합니다. 이 경우에는 현재 위치에 새로운 꽃을 심어주고 큐에 추가합니다.
- else if(garden[nr][nc].kind == RED && temp.kind == GREEN): 이 부분은 이동하려는 꽃의 색이 빨간색이고 현재 위치의 꽃이 초록색인 경우를 다룹니다. 만약 두 꽃이 같은 시간대에 이동한다면(현재 꽃의 시간 + 1), 이미 핀 꽃으로 표시하고 이미 핀 꽃의 수를 증가시킵니다.
- else if(garden[nr][nc].kind == GREEN && temp.kind == RED): 이 부분은 이동하려는 꽃의 색이 초록색이고 현재 위치의 꽃이 빨간색인 경우를 다룹니다. 마찬가지로 두 꽃이 같은 시간대에 이동한다면(현재 꽃의 시간 + 1), 이미 핀 꽃으로 표시하고 이미 핀 꽃의 수를 증가시킵니다.
- else: 이 부분은 나머지 경우를 다룹니다. 즉, 현재 위치에 꽃이 없는 경우이거나, 두 꽃의 색이 같지 않은 경우를 말합니다. 이 경우에도 새로운 꽃을 심어주고 큐에 추가합니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M, G, R;
public static int[][] map;
public static int answer = 0;
public static int GREEN = 2601, RED = 2602, ALREADYFLOWERED = 2603;
public static Flower[] selectedComb;
public static ArrayList<int[]> flowerableList = new ArrayList<>();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
G = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
// 0 : 호수 1 : (배양액을 뿌릴 수 없는 땅) 2 : 배양액을 뿌릴 수 있는 땅
map = new int[N][M];
selectedComb = new Flower[G+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) {
flowerableList.add(new int[] {i, j});
}
}
}
simulate(0, 0, 0, 0);
System.out.println(answer);
}
public static void simulate(int level, int selectedIndex, int green, int red) {
//만약 배양액을 모두 뿌렸다면 해당 Map에서 피울 수 있는 꽃의 최대 개수를 구할 것 입니다.
if(green == G && red == R) {
getFlowerSimulate();
return ;
}
if(selectedIndex >= flowerableList.size() || level >= G+R) {
return ;
}
int row = flowerableList.get(selectedIndex)[0];
int col = flowerableList.get(selectedIndex)[1];
//만약 배양액을 뿌릴 수 있는 땅이라면,
if(map[row][col] == 2) {
//아직 초록색 배양액을 뿌릴 수 있다면,
if(green < G) {
selectedComb[level] = new Flower(row, col, GREEN, 0);
map[row][col] = GREEN;
simulate(level + 1, selectedIndex + 1, green + 1, red);
map[row][col] = 2;
}
//아직 빨간색 배양액을 뿌릴 수 있다면,
if(red < R) {
selectedComb[level] = new Flower(row, col, RED, 0);
map[row][col] = RED;
simulate(level + 1, selectedIndex + 1, green, red + 1);
map[row][col] = 2;
}
}
//아무것도 뿌리지 않고 지나가는 경우도 있을 것 입니다.
simulate(level, selectedIndex + 1 , green, red);
}
public static void getFlowerSimulate() {
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
Flower[][] garden = new Flower[N][M];
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
garden[i][j] = new Flower();
garden[i][j].time = Integer.MAX_VALUE;
garden[i][j].kind = 0;
}
}
Queue<Flower> q = new LinkedList<>();
//빨간색 배양액과 초록색 배양액을 하나의 큐에 넣어준다.
//이떄 큐에 빨간색인지, 초록색인지 구분하는 변수도 추가해준다.
for(int i=0;i<G+R;i++) {
q.offer(new Flower(selectedComb[i].r, selectedComb[i].c, selectedComb[i].kind, selectedComb[i].time));
garden[selectedComb[i].r][selectedComb[i].c].time = 0;
garden[selectedComb[i].r][selectedComb[i].c].kind = selectedComb[i].kind;
}
int alreadyFloweredCnt = 0;
while(!q.isEmpty()) {
Flower temp = q.poll();
//만약 해당 큐가 시작하려고하는데 이미 꽃이 핀 곳이었다면, 큐가 작동하지 않게 합니다.
if(garden[temp.r][temp.c].kind == ALREADYFLOWERED) {
continue;
}
for(int dir = 0; dir < 4; dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
//만약 범위를 벗어나면 큐가 작동하지 않습니다.
if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
//만약 호수라면 큐가 작동하지 않습니다.
if(map[nr][nc] == 0) continue;
if(garden[nr][nc].time <= temp.time) continue; // 만약 현재 시간과 같을경우에도 이동하지 못하게 처리해야한다. 그렇지 않으면 무한반복이 걸린다.
//만약 이미 합쳐진 곳이라면 큐가 작동하지 않습니다.
if(garden[nr][nc].kind == ALREADYFLOWERED) continue;
//만약 이동할곳이 빨간색이라면, time[][] 배열을 통해 같은 시간대라면 합쳐주고, 같은 시간대가 아니라면 continue 시킵니다.
else if(garden[nr][nc].kind == RED && temp.kind == GREEN) {
//이 경우에는 따로 큐에 안넣어도 됩니다.
if(garden[nr][nc].time == temp.time + 1) {
garden[nr][nc].kind = ALREADYFLOWERED;
garden[nr][nc].time = temp.time + 1;
alreadyFloweredCnt += 1;
}
}
//만약 이동할 곳에 이미 RED가 존재하는데 time마저 같다면, 합쳐줄 것 입니다.
else if(garden[nr][nc].kind == GREEN && temp.kind == RED) {
// System.out.println("FIND APPOCALPYSE");
//이 경우에는 따로 큐에 안넣어도 됩니다.
if(garden[nr][nc].time == temp.time + 1) {
garden[nr][nc].kind = ALREADYFLOWERED;
garden[nr][nc].time = temp.time + 1;
alreadyFloweredCnt += 1;
}
}
//색이 안차있는 경우 넘겨줍니다.
else if( (garden[nr][nc].kind == GREEN && temp.kind == GREEN)|| (garden[nr][nc].kind == RED && temp.kind == RED)){
garden[nr][nc].time = temp.time + 1;
garden[nr][nc].kind = temp.kind;
q.offer(new Flower(nr, nc, temp.kind, temp.time + 1));
}
//색이 안차있는 경우 넘겨줍니다.
else {
garden[nr][nc].time = temp.time + 1;
garden[nr][nc].kind = temp.kind;
q.offer(new Flower(nr, nc, temp.kind, temp.time + 1));
}
}
answer = Math.max(answer, alreadyFloweredCnt);
}
}
}
class Flower{
int r;
int c;
int kind;
int time;
public Flower(int r, int c, int kind, int time) {
this.r=r;
this.c=c;
this.kind = kind;
this.time = time;
}
public Flower() {
}
}
배양액을 둘 수 있는 flowerableList와 selectedComb를 활용하여 선택할 배양액을 선택하였습니다.
하지만, 여전히 시간초과가 발생합니다.
의심되는 부분으로는, BFS내에서 꽃을 펼쳐주는 부분의 로직에 있어서 문제가 있다고 생각됩니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M, G, R;
public static int[][] map;
public static int answer = 0;
public static int GREEN = -98, RED = -99, ALREADYFLOWERED = -1000;
public static Flower[] selectedComb;
public static ArrayList<int[]> flowerableList = new ArrayList<>();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
G = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
// 0 : 호수 1 : (배양액을 뿌릴 수 없는 땅) 2 : 배양액을 뿌릴 수 있는 땅
map = new int[N][M];
selectedComb = new Flower[G+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) {
flowerableList.add(new int[] {i, j});
}
}
}
simulate(0, 0, 0, 0);
System.out.println(answer);
}
public static void simulate(int level, int selectedIndex, int green, int red) {
//만약 배양액을 모두 뿌렸다면 해당 Map에서 피울 수 있는 꽃의 최대 개수를 구할 것 입니다.
if(green == G && red == R) {
getFlowerSimulate();
return ;
}
if(selectedIndex >= flowerableList.size() || level >= G+R) {
return ;
}
int row = flowerableList.get(selectedIndex)[0];
int col = flowerableList.get(selectedIndex)[1];
//만약 배양액을 뿌릴 수 있는 땅이라면,
if(map[row][col] == 2) {
//아직 초록색 배양액을 뿌릴 수 있다면,
if(green < G) {
selectedComb[level] = new Flower(row, col, GREEN, 0);
map[row][col] = GREEN;
simulate(level + 1, selectedIndex + 1, green + 1, red);
map[row][col] = 2;
}
//아직 빨간색 배양액을 뿌릴 수 있다면,
if(red < R) {
selectedComb[level] = new Flower(row, col, RED, 0);
map[row][col] = RED;
simulate(level + 1, selectedIndex + 1, green, red + 1);
map[row][col] = 2;
}
}
//아무것도 뿌리지 않고 지나가는 경우도 있을 것 입니다.
simulate(level, selectedIndex + 1 , green, red);
}
public static void getFlowerSimulate() {
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
Flower[][] garden = new Flower[N][M];
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
garden[i][j] = new Flower();
garden[i][j].time = Integer.MAX_VALUE;
}
}
Queue<Flower> q = new LinkedList<>();
//빨간색 배양액과 초록색 배양액을 하나의 큐에 넣어준다.
//이떄 큐에 빨간색인지, 초록색인지 구분하는 변수도 추가해준다.
for(int i=0;i<G+R;i++) {
q.offer(selectedComb[i]);
garden[selectedComb[i].r][selectedComb[i].c].time = 0;
garden[selectedComb[i].r][selectedComb[i].c].kind = selectedComb[i].kind;
}
int alreadyFloweredCnt = 0;
while(!q.isEmpty()) {
Flower temp = q.poll();
//만약 해당 큐가 시작하려고하는데 이미 꽃이 핀 곳이었다면, 큐가 작동하지 않게 합니다.
if(garden[temp.r][temp.c].kind == ALREADYFLOWERED) {
continue;
}
for(int dir = 0; dir < 4; dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
//만약 범위를 벗어나면 큐가 작동하지 않습니다.
if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
//만약 호수라면 큐가 작동하지 않습니다.
if(map[nr][nc] == 0) continue;
if(garden[nr][nc].time <= temp.time) continue; // 만약 현재 시간과 같을경우에도 이동하지 못하게 처리해야한다. 그렇지 않으면 무한반복이 걸린다.
//만약 이미 합쳐진 곳이라면 큐가 작동하지 않습니다.
if(garden[nr][nc].kind == ALREADYFLOWERED) {
continue;
}
//만약 이동할곳이 빨간색이라면, time[][] 배열을 통해 같은 시간대라면 합쳐주고, 같은 시간대가 아니라면 continue 시킵니다.
else if(garden[nr][nc].kind == RED && temp.kind == GREEN) {
//이 경우에는 따로 큐에 안넣어도 됩니다.
if(garden[nr][nc].time == temp.time + 1) {
garden[nr][nc].kind = ALREADYFLOWERED;
garden[nr][nc].time = temp.time + 1;
alreadyFloweredCnt += 1;
}
}
//만약 이동할 곳에 이미 RED가 존재하는데 time마저 같다면, 합쳐줄 것 입니다.
else if(garden[nr][nc].kind == GREEN && temp.kind == RED) {
// System.out.println("FIND APPOCALPYSE");
//이 경우에는 따로 큐에 안넣어도 됩니다.
if(garden[nr][nc].time == temp.time + 1) {
garden[nr][nc].kind = ALREADYFLOWERED;
garden[nr][nc].time = temp.time + 1;
alreadyFloweredCnt += 1;
}
}
//색이 안차있는 경우 넘겨줍니다.
else {
// System.out.println("nr;"+nr+"nc:"+nc);
garden[nr][nc].time = temp.time + 1;
garden[nr][nc].kind = temp.kind;
q.offer(new Flower(nr, nc, temp.kind, temp.time + 1));
}
}
answer = Math.max(answer, alreadyFloweredCnt);
}
}
}
class Flower{
int r;
int c;
int kind;
int time;
public Flower(int r, int c, int kind, int time) {
this.r=r;
this.c=c;
this.kind = kind;
this.time = time;
}
public Flower() {
}
}
시간초과나는경우
처음에 무한반복 걸렸었던 부분은 새로 이동할 부분과 현재 이동할 시간이 같은경우에도, time 은 이동하면 다음 시간대로 인식하니 무시하고 넘어가야합니다.
if(time[nr][nc] <= temp.time) continue; // 만약 현재 시간과 같을경우에도 이동하지 못하게 처리해야한다. 그렇지 않으면 무한반복이 걸린다.또한, alreadyFloweredCnt 부분에서 꽃이 핀 횟수를 굳이 마지막에 반복문을 사용하지 않고, 꽃이 필때마다 처리하도록 해줍니다.
아래의 코드에서 문제점은 모든 배양액을 설정할떄마다 storeMap을 통해서 새로 배열을 만든뒤 getFlowerSimulate(storeMap)을 통해 꽃을 피도록 설정하는 부분에 있어서 시간초과가 발생합니다.
int[][] storeMap = new int[N][M];
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
storeMap[i][j] = map[i][j];
}
}
getFlowerSimulate(storeMap);import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M, G, R;
public static int[][] map;
public static int answer = 0;
public static int GREEN = -98, RED = -99, ALREADYFLOWERED = -1000;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
G = Integer.parseInt(st.nextToken());
R = Integer.parseInt(st.nextToken());
// 0 : 호수 1 : (배양액을 뿌릴 수 없는 땅) 2 : 배양액을 뿌릴 수 있는 땅
map = new int[N][M];
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());
}
}
simulate(0, 0, 0, 0, 0);
System.out.println(answer);
}
public static void simulate(int level, int row, int col, int green, int red) {
if(col >= M) {
col = 0;
row = row + 1;
}
//만약 배양액을 모두 뿌렸다면 해당 Map에서 피울 수 있는 꽃의 최대 개수를 구할 것 입니다.
if(green == G && red == R ) {
int[][] storeMap = new int[N][M];
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
storeMap[i][j] = map[i][j];
}
}
getFlowerSimulate(storeMap);
return ;
}
if(row >= N) {
return ;
}
//만약 배양액을 뿌릴 수 있는 땅이라면,
if(map[row][col] == 2) {
//아직 초록색 배양액을 뿌릴 수 있다면,
if(green < G) {
map[row][col] = GREEN;
simulate(level + 1, row, col + 1, green + 1, red);
map[row][col] = 2;
}
//아직 빨간색 배양액을 뿌릴 수 있다면,
if(red < R) {
map[row][col] = RED;
simulate(level + 1, row, col + 1, green, red + 1);
map[row][col] = 2;
}
}
//아무것도 뿌리지 않고 지나가는 경우도 있을 것 입니다.
simulate(level + 1, row, col + 1, green, red);
}
public static void getFlowerSimulate(int[][] mapTemp) {
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
int[][] time = new int[N][M];
for(int i=0;i<N;i++) {
Arrays.fill(time[i], Integer.MAX_VALUE);
}
Queue<Flower> q = new LinkedList<>();
//빨간색 배양액과 초록색 배양액을 하나의 큐에 넣어준다.
//이떄 큐에 빨간색인지, 초록색인지 구분하는 변수도 추가해준다.
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
if(mapTemp[i][j] == GREEN) {
q.offer(new Flower(i, j, GREEN, 0));
time[i][j] = 0;
}
else if(mapTemp[i][j] == RED) {
q.offer(new Flower(i, j, RED, 0));
time[i][j] = 0;
}
}
}
int alreadyFloweredCnt = 0;
while(!q.isEmpty()) {
Flower temp = q.poll();
//만약 해당 큐가 시작하려고하는데 이미 꽃이 핀 곳이었다면, 큐가 작동하지 않게 합니다.
if(mapTemp[temp.r][temp.c] == ALREADYFLOWERED) {
continue;
}
for(int dir = 0; dir < 4; dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
//만약 범위를 벗어나면 큐가 작동하지 않습니다.
if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
//만약 호수라면 큐가 작동하지 않습니다.
if(mapTemp[nr][nc] == 0) continue;
if(time[nr][nc] <= temp.time) continue; // 만약 현재 시간과 같을경우에도 이동하지 못하게 처리해야한다. 그렇지 않으면 무한반복이 걸린다.
//만약 이미 합쳐진 곳이라면 큐가 작동하지 않습니다.
if(mapTemp[nr][nc] == ALREADYFLOWERED) {
continue;
}
//만약 이동할곳이 빨간색이라면, time[][] 배열을 통해 같은 시간대라면 합쳐주고, 같은 시간대가 아니라면 continue 시킵니다.
else if(mapTemp[nr][nc] == RED && temp.kind == GREEN) {
//이 경우에는 따로 큐에 안넣어도 됩니다.
if(time[nr][nc] == temp.time + 1) {
mapTemp[nr][nc] = ALREADYFLOWERED;
time[nr][nc] = temp.time + 1;
alreadyFloweredCnt += 1;
}
}
//만약 이동할 곳에 이미 RED가 존재하는데 time마저 같다면, 합쳐줄 것 입니다.
else if(mapTemp[nr][nc] == GREEN && temp.kind == RED) {
// System.out.println("FIND APPOCALPYSE");
//이 경우에는 따로 큐에 안넣어도 됩니다.
if(time[nr][nc] == temp.time + 1) {
mapTemp[nr][nc] = ALREADYFLOWERED;
time[nr][nc] = temp.time + 1;
alreadyFloweredCnt += 1;
}
}
//색이 안차있는 경우 넘겨줍니다.
else {
time[nr][nc] = temp.time + 1;
mapTemp[nr][nc] = temp.kind;
q.offer(new Flower(nr, nc, temp.kind, temp.time + 1));
}
}
answer = Math.max(answer, alreadyFloweredCnt);
}
}
}
class Flower{
int r;
int c;
int kind;
int time;
public Flower(int r, int c, int kind, int time) {
this.r=r;
this.c=c;
this.kind = kind;
this.time = time;
}
}
시간초과 나는 코드입니다.
사용할 배양지를 조합, 완전탐색으로 구한 후에
순열을 구한후 BFS를 구했기에 시간초과가 납니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N, M, K, G, R;
public static int[][] map;
public static int answer = 0;
public static int[] dx = {-1,1,0,0};
public static int[] dy = {0,0,-1,1};
public static Node[] selectedComb;
public static int[] greenRed;
public static boolean[] greenRedVisited;
public static int[][] visited;
public static int GREEN_NUM = 20, RED_NUM = 30, FLOWER_NUM = 40;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
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];
greenRed = new int[G + R];
selectedComb = new Node[G + 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()); // 0 : 호수, 1 : 배양액X 2 : 배양액가능.
}
}
int greenRedIdx = 0;
for(int i=0;i<G;i++) {
greenRed[greenRedIdx++] = GREEN_NUM;
}
for(int i=0;i<R;i++) {
greenRed[greenRedIdx++] = RED_NUM;
}
//1. 초록색 배양액과 빨간색 배양액의 개수만큼 땅을 조합으로 선택하고, 선택된 조합( (1,1), (2,3) (4,5) )가 선택되었다고 했을때 배양액이 G : 1 R : 2 개 있으면, GGR, GRG, RGG 이렇게 나타내기 위해 순열을 선택한다.
selectComb(0, 0, 0);
System.out.println(answer);
}
public static void selectComb(int level, int r, int c) {
if(level == G + R) {
greenRedVisited = new boolean[G+R];
//selectedComb[배양액 개수] : 배양액의 개수마다의 위치가 정해졌다.
getNormalPermutation(0);
return ;
}
for(int i=r; i<N ;i++) {
for(int j=( i == r ? c : 0); j<M;j++) {
if(map[i][j] != 2) continue;
map[i][j] = 10; //선택되었다는 의미입니다
selectedComb[level] = new Node(i, j, 0, 1);
selectComb(level + 1, i, j + 1); //j+1이 넘어가면 자동으로 작동하지않습니다.
map[i][j] = 2;
}
}
}
public static void getNormalPermutation(int level) {
if(level == G+R) {
answer = Math.max(answer, BFS());
return ;
}
for(int i=0;i<G+R;i++) {
if(greenRedVisited[i] == false) {
greenRedVisited[i] = true;
selectedComb[level].type = greenRed[i];
getNormalPermutation(level + 1);
greenRedVisited[i] = false;
}
}
}
public static int BFS() {
Queue<Node> q = new LinkedList<>();
visited = new int[N][M];
for(int i=0;i<selectedComb.length;i++) {
q.offer(selectedComb[i]);
if(selectedComb[i].type == GREEN_NUM) {
visited[selectedComb[i].r][selectedComb[i].c] = 1;
}else if(selectedComb[i].type == RED_NUM) {
visited[selectedComb[i].r][selectedComb[i].c] = -1;
}
}
while(!q.isEmpty()) {
Node temp = q.poll();
if(visited[temp.r][temp.c]== FLOWER_NUM) {
continue;
}
for(int dir = 0; dir < 4; dir++) {
int nr = temp.r + dx[dir];
int nc = temp.c + dy[dir];
if(nr < 0 || nr >= N || nc < 0 || nc >= M) continue;
if(map[nr][nc] == 0) continue; //만약 호수인경우.
if(visited[nr][nc] == FLOWER_NUM) continue;
//만약 초록용액이라면,
if(temp.type == GREEN_NUM) {
//아무것도 없을시에는 바로 이동.
if(visited[nr][nc] == 0) {
visited[nr][nc] = temp.cnt + 1;
q.offer(new Node(nr, nc, temp.type, temp.cnt + 1));
}
if(visited[nr][nc] > 0) {
continue;
}
if(visited[nr][nc] < 0) {
if(visited[nr][nc] + ( temp.cnt + 1 )== 0) {
visited[nr][nc] = FLOWER_NUM; //꽃이피면 q에 넣지않는다.
}
}
}
//만약 빨간용액이라면,
else if(temp.type == RED_NUM) {
//아무것도 없을시에는 바로 이동.
if(visited[nr][nc] == 0) {
visited[nr][nc] = -(temp.cnt + 1);
q.offer(new Node(nr, nc, temp.type, temp.cnt + 1));
}
if(visited[nr][nc] < 0) {
continue;
}
if(visited[nr][nc] > 0) {
if(visited[nr][nc] - (temp.cnt + 1) == 0) {
visited[nr][nc] = FLOWER_NUM; //꽃이피면 q에 넣지않는다.
}
}
}
}
}
int flowerResult = 0;
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
if(visited[i][j] == FLOWER_NUM) {
flowerResult += 1;
}
}
}
return flowerResult;
}
}
class Node{
int r;
int c;
int type; //20 : 초록색, 30 : 빨간색
int cnt = 0;
public Node(int r, int c, int type) {
this.r = r;
this.c = c;
this.type = type;
}
public Node(int r, int c, int type, int cnt) {
this.r = r;
this.c = c;
this.type = type;
this.cnt = cnt;
}
}