알고리즘/완전탐색(BFS,DFS)
BOJ - 18809 ) Gaaaaaaaaaarden
개발자가될수있을까?
2020. 5. 28. 18:18
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
입력으로부터 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;
}
}
}
}