BOJ - 18809 ) Gaaaaaaaaaarden

 

---

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

18809번: Gaaaaaaaaaarden

 

---

입력으로부터 2인 배양가능한 장소를 적절한 부분집합으로 나누어 (DFS) 

 

시간이같은상황에서 서로다른 색깔 (BFS)를 이용하여 판단하는문제

 

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Gaaaaaaaaaarden{
	public static int N,M,Map[][],Rmax,Gmax,Answer,size;
	public static int [][] colors;
	public static int dir[][] = {{1,0},{-1,0},{0,1},{0,-1}};
	public static ArrayList <int []>  al = new ArrayList<>();
	public static ArrayDeque<int []>  dq = new ArrayDeque<>();
 	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N    = Integer.parseInt(st.nextToken());
		M    = Integer.parseInt(st.nextToken());
		Rmax = Integer.parseInt(st.nextToken());
		Gmax = Integer.parseInt(st.nextToken());
		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) {
					al.add(new int[] {i,j});
				}
			}
		}
		size = al.size();
		colors = new int[Rmax+Gmax][2];
		DFS(0,0,0,0);
		System.out.println(Answer);
	}
	private static void DFS(int index, int R, int G,int colorIndex) {
		if(R==Rmax&& G==Gmax) {
			//여기서 bfs실행
			int res = 0;
			int y = 0 , x = 0;
			int visit[][][] = new int[N][M][3];
			for(int i = 0 ; i < colorIndex ; i++) {
				if(colors[i][1] ==1) { // red
					y = al.get(colors[i][0])[0];
					x = al.get(colors[i][0])[1];
					visit[y][x][0] =1;
					visit[y][x][1] =1;
					visit[y][x][2] =3;
					dq.add(new int[] {y,x,1,3});
				}
				if(colors[i][1] ==2) { // green
					y = al.get(colors[i][0])[0];
					x = al.get(colors[i][0])[1];
					visit[y][x][0] =1;
					visit[y][x][1] =1;
					visit[y][x][2] =4;
					dq.add(new int[] {y,x,1,4}); 
				}
			}
				while(!dq.isEmpty()) {
					int []now = dq.poll();
					if(visit[now[0]][now[1]][2] ==7) continue;
					for(int j = 0 ; j < 4 ; j ++) {
						int ny = now[0] + dir[j][0];
						int nx = now[1] + dir[j][1];
						if(ny>=0&&nx>=0&&nx<M&&ny<N&&Map[ny][nx]!=0) {
							if(visit[ny][nx][0]==0) {
								visit[ny][nx][0]=1;
								visit[ny][nx][1]=now[2]+1;
								visit[ny][nx][2]=now[3];
								dq.add(new int[] {ny,nx,now[2]+1,now[3]});
							}
							if(visit[ny][nx][0]==1) {
								if( visit[ny][nx][2]+now[3] == 7 && (now[2]+1)==visit[ny][nx][1]) {
									visit[ny][nx][2]+=now[3];
									res++;
								}
							}
						}
					}
				}
			if(res > Answer) Answer = res;
			return;
		}
		for(int i = index ; i < size ; i++) {
			if(R < Rmax) {
				colors[colorIndex][0] = i;
				colors[colorIndex][1] = 1;
				DFS(i+1,R+1,G,colorIndex+1);
				colors[colorIndex][0] = 0;
				colors[colorIndex][1] = 0;
			}
			if(G < Gmax) {
				colors[colorIndex][0] = i;
				colors[colorIndex][1] = 2;
				DFS(i+1,R,G+1,colorIndex+1);
				colors[colorIndex][0] = 0;
				colors[colorIndex][1] = 0;
			}
		}
	}
}

---