[백준] Gaaaaaaaaaarden 18809 - JAVA

문제

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

18809번: Gaaaaaaaaaarden

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Pos {
	int x;
	int y;

	Pos(int x, int y){
		this.x = x;
		this.y = y;
	}
}

class Pair{
	int time;
	int type;
	Pair(){

	}
	Pair(int time, int type){
		this.time = time;
		this.type = type;
	}
}

class Main{
	static int row, col;
	static int green, red;
	static int[][] board;
	static ArrayList<Pos> possible;
	static boolean[] visited;
	static int[] greens, reds;
	static int max;
	static final int RED = 3;
	static final int GREEN = 4;
	static final int FLOWER = 5;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		row = Integer.parseInt(st.nextToken());
		col = Integer.parseInt(st.nextToken());
		green = Integer.parseInt(st.nextToken());
		red = Integer.parseInt(st.nextToken());
		possible = new ArrayList<>();

		
		board = new int[row][col];
		for(int i=0; i<row; i++){
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<col; j++){
				board[i][j] = Integer.parseInt(st.nextToken());
				if(board[i][j] == 2)
					possible.add(new Pos(i,j));
			}
		}

		greens = new int[green];
		reds = new int[red];
		visited = new boolean[10];
		perm_green(0, 0);
		System.out.println(max);
	}

	private static void perm_green(int start, int cnt){
		if(cnt == green){
			perm_red(0, 0);
			return;
		}

		for(int i=start; i<possible.size(); i++){
			if(!visited[i]){
				visited[i] = true;
				greens[cnt] = i;
				perm_green(i+1, cnt+1);
				visited[i] = false;
			}
		}
	}

	private static void perm_red(int start, int cnt){
		if(cnt == red){
			bfs();
			return;
		}

		for(int i=start; i<possible.size(); i++){
			if(!visited[i]){
				visited[i] = true;
				reds[cnt] = i;
				perm_red(i+1, cnt+1);
				visited[i] = false;
			}
		}
	}

	private static void bfs(){
		Queue<Pos> que = new LinkedList<>();
		Pair[][] state = new Pair[row][col];

		// state 초기화
		for(int i=0; i<row; i++)
			for(int j=0; j<col; j++)
				state[i][j] = new Pair();

		// 배양지로 선택한 곳에 배양액 놓기
		for(int i=0; i<red; i++){
			Pos p = possible.get(reds[i]);
			state[p.x][p.y] = new Pair(0, RED);
			que.offer(new Pos(p.x, p.y));
		}
		
		for(int i=0; i<green; i++){
			Pos p = possible.get(greens[i]);
			state[p.x][p.y] = new Pair(0, GREEN);
			que.offer(new Pos(p.x, p.y));
		}

		int sum = 0;

		int[] dx = {-1,1,0,0};
		int[] dy = {0,0,-1,1};
		
		while(!que.isEmpty()){
			Pos p =que.poll();
			int x = p.x;
			int y = p.y;
			int curtime = state[x][y].time;
			int curtype = state[x][y].type;

			if(state[x][y].type == FLOWER) continue;

			for(int i=0; i<4; i++){
				int nx = x + dx[i];
				int ny = y + dy[i];

				if(isValidPosition(nx, ny) && board[nx][ny] != 0){
					// 아직 배양액이 퍼지지 않았다면 퍼트림
					if(state[nx][ny].type == 0){
						state[nx][ny] = new Pair(curtime+1, curtype);
						que.offer(new Pos(nx, ny));
					}
					// 빨간색이 있을때 초록색이 퍼지는 거라면 꽃을 피우고 count
					else if(state[nx][ny].type == RED){
						if(curtype == GREEN && state[nx][ny].time == curtime + 1){
							sum++;
							state[nx][ny].type = FLOWER;
						}
					}
					// 초록색이 있을때 빨간색이 퍼지는 거라면 꽃을 피우고 count
					else if(state[nx][ny].type == GREEN){
						if(curtype == RED && state[nx][ny].time == curtime + 1){
							sum++;
							state[nx][ny].type = FLOWER;
						}
					}
				}
			}
		}

		max = max < sum ? sum : max;
	}

	private static boolean isValidPosition(int x, int y){
		if(x < 0 || y < 0 || x >= row || y >= col) return false;
		return true;
	}
}