가든 [백준 18809][JAVA][골드1][조합][BFS]

 

[광고 누르면 오늘의 행운 상승!!]

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

18809번: Gaaaaaaaaaarden

구현이 까다로운 조합 + BFS문제이다. 
처음에는 순열로 구현하여 MAP으로 중복처리를 했는데 수행속도가 3900ms가 나왔다.
2번의 조합으로 변경했더니 800~900ms까지 떨어졌다.

1. 참고사항

- list를 사용하여 심을 수 있는 땅의 위치를 저장했다.
- 두번의 조합을 사용하여 Green 배양액을 먼저 심고 Red 배양액을 심어서
  나온 결과를 토대로 bfs를 돌렸다.
- map정보를 이용하여 풀었기 때문에 CopyMap함수를 이용하여 복사한 맵을 전달했다.
- growMap 배열을 이용하여 퍼져나가는 시간을 관리했다. -> 동시에 번진 땅 == 꽃이 필 수 있는 위치 를 구하기 위함.

2. 구현

- map을 담으면서 값이 2면 list에 담았다 ( 배양액을 심을 수 있는 땅) 그후 1로 변경( 이동할 수 있는 땅)
- G+R개수의 ground 배열을 이용하여 G개의 조합을 뽑아 낸 후 R개의 조합을 추가로 뽑아내어 
  Green, Red 배양액이 위치할 수 있는 곳을 조합으로 뽑아내었다.
- ground배열을 토대로 bfs를 시작했다. Gwater , Rwater 두개의 큐를 이용하여 배양액의
  초기위치와 map의 정보를 바꾸어 주었다.
- 두개의 큐를 각 사이즈만큼 돌아 1타임씩 관리했다. (qsize 전부 돌고 rsize 전부 돌면 한타임)
- 배양액이 자신과 다른 색을 만나고 자신과 같은 타임이면 꽃을 생성하고 호수로 변경(0) 
- 그게 아니면 퍼져나간다.
- rsize와 gsize가 모두 0이면 빠져나간다.
- 꽃이 핀 개수를 ans에 갱신한다.
- 최종 ans를 출력 

package Study9;

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

public class 가든 {
	static class Water{
		int row, col, time;
		public Water(int row, int col,int time) {
			this.row = row;
			this.col = col;
			this.time = time;
		}
	}
	static ArrayList<int[]> list;
	static int[] dx = {-1,0,1,0};
	static int[] dy = {0,1,0,-1};
	static int[][] map;
	static boolean[] v;
	static boolean[][] visit;
	static int N,M,ans,G,R,gcnt;
	static int[] ground;
	static int Green = 100, Red = 101;
    static int flower;
	static int[][] growMap;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("test.txt"));
		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());
		list = new ArrayList<>();
		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());
				if(map[i][j] == 2) {
					gcnt++;
					list.add(new int[]{i,j});
					map[i][j] = 1;
				}
			}
		}
		v = new boolean[gcnt];
		ground = new int[G+R];
		
		dfs(0,Green,0,0);
		
		System.out.println(ans);
	}
	private static void dfs(int start ,int color, int cnt, int temp) {
		if(color == Green && cnt == G) {
			dfs(0,Red,0,cnt);
			return;
		}else if(color == Red && cnt == R) {
			bfs(copyMap(map));
			ans = Math.max(flower, ans);
			return;
		}
		for (int i = start; i < gcnt; i++) {
			if(!v[i]) {
				v[i] = true;
				ground[cnt+temp] = i;
				dfs(i, color, cnt+1,temp);
				v[i] = false;
			}
		}
	}
	private static int[][] copyMap(int[][] map) {
		int[][] copyMap = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				copyMap[i][j] = map[i][j];
			}
		}
		return copyMap;
	}
	private static void bfs(int[][] map) {
		System.out.println(Arrays.toString(ground));
		flower = 0;
		visit = new boolean[N][M];
		growMap = new int[N][M];
		
		Queue<Water> GWater = new LinkedList<>();
		Queue<Water> RWater = new LinkedList<>();
		
		for (int i = 0; i < G; i++) {
			int row = list.get(ground[i])[0];
			int col = list.get(ground[i])[1];
			GWater.add(new Water(row,col,0));
			map[row][col] = Green;
			visit[row][col] = true;
		}
		for (int i = G; i < G+R; i++) {
			int row = list.get(ground[i])[0];
			int col = list.get(ground[i])[1];
			RWater.add(new Water(row,col,0));
			map[row][col] = Red;
			visit[row][col] = true;
		}
		
		while(true) {
			int Gsize = GWater.size();
			for (int s = 0; s < Gsize; s++) {
				Water gwater = GWater.poll();
				if(map[gwater.row][gwater.col] == 0) continue;
				
				for (int dir = 0; dir < 4; dir++) {
					int nx = gwater.row + dx[dir];
					int ny = gwater.col + dy[dir];
					
					if(check(nx, ny)) continue;
					
					if(map[nx][ny] == 0 || map[nx][ny] == Green ) continue;
					
					if(map[nx][ny] == Red && growMap[nx][ny] == gwater.time+1) {
						map[nx][ny] = 0;
						flower++;
					}else if(map[nx][ny] == 1) {
						map[nx][ny] = Green;
						growMap[nx][ny] = gwater.time+1;
						GWater.add(new Water(nx,ny,gwater.time+1));
					}
				}
			}
			
			int Rsize = RWater.size();
			for (int s = 0; s < Rsize; s++) {
				Water rwater = RWater.poll();
				if(map[rwater.row][rwater.col] == 0) continue;
				
				for (int dir = 0; dir < 4; dir++) {
					int nx = rwater.row + dx[dir];
					int ny = rwater.col + dy[dir];
					
					if(check(nx, ny)) continue;
					
					if(map[nx][ny] == 0 || map[nx][ny] == Red) continue;
					
					if(map[nx][ny] == Green && growMap[nx][ny] == rwater.time+1) {
						map[nx][ny] = 0;
						flower++;
					}else if(map[nx][ny] == 1) {
						map[nx][ny] = Red;
						growMap[nx][ny] = rwater.time+1;
						RWater.add(new Water(nx,ny,rwater.time+1));
					}
				}
			}
			
			if(Gsize == 0 && Rsize ==0) break;
		}
	}
	private static boolean check(int nx, int ny) {
		return nx < 0 || nx >= N || ny < 0 || ny >= M;
	}
}