[백준 18809] Gaaaaaaaaaarden(JAVA)

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

18809번: Gaaaaaaaaaarden

 

백준에서 진행한 코딩테스트 대비 모의고사 문제이다. 삼성 코테대비로 풀어봤다. 

배양액을 놓을 수 있는 자리를 soil 어레이리스트에 미리 넣어두었다.

그 다음 배양액을 놓을 수 있는 자리에 dfs로 빨간색을 먼저 다 놔준 다음 , 초록색을 놔줬다.

같은 턴에 확산된 자리인지 확인하기 위해 visit 배열에 time값을 넣어주었다

그 다음 bfs로 빨간색을 먼저 확산시켜준 다음, 초록색을 확산시킬 때 같은 턴에 빨간색이 확산시킨 곳이라면 (visit배열의 값이 같으면)

map값을 10으로 바꿔주어 꽃으로 표시해주었다.

 

시간초과로 몇번 틀린 문제이다.

visit배열을 매턴마다 초기화해주어서 시간초과가 났다. 한 번만 초기화해두고 time값을 넣어주고 비교하는 방법으로 바꾸니 통과되었다.

package 코테대비모의고사;

//4:17~
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

class Pos {
	int x;
	int y;
	boolean chk;

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

	public Pos(int x, int y, boolean chk) {
		super();
		this.x = x;
		this.y = y;
		this.chk = chk;
	}

}

public class Main_bj_18809_Gaaaaaaaaaarden {

	static int N, M, G, R;// 행,열,초록,빨강
	static int[][] map;
	static int ans = 0;
	static List<Pos> soil, red, green;
	static int[] dx= {0,0,1,-1};
	static int[] dy= {1,-1,0,0};

	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());
		G = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		map = new int[N][M];// 0호수, 1배양액 뿌릴수X, 2배양액 뿌릴수O
		soil = new ArrayList<Pos>();
		red = new ArrayList<Pos>();
		green = new ArrayList<Pos>();
		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) {
					soil.add(new Pos(i, j, false));
				}
			}
		} // 입력끝
		
		inject(0, -1,0);// 빨강 먼저 놓기
		
		System.out.println(ans);
	}

	private static void inject(int cnt, int color,int index) {// -1빨강 -2초록
		if (color == -1 && cnt == R) {// 빨강색 다놓았으면
			inject(0, -2,0);
			return;
		}
		if (color == -2 && cnt == G) {// 초록색 다놓았으면
			bfs();// 퍼뜨려서 답구하기
			return;
		}
		for (int i = index; i < soil.size(); i++) {
			Pos p = soil.get(i);
			if (p.chk == false) {
				p.chk = true;
				map[p.x][p.y] = color;
				if (color == -1) {
					red.add(new Pos(p.x, p.y));
				}
				if (color == -2) {
					green.add(new Pos(p.x, p.y));
				}
				inject(cnt + 1, color,i+1);
				p.chk = false;
				if (color == -1) {
					red.remove(red.size()-1);
				}
				if (color == -2) {
					green.remove(green.size()-1);
				}
				map[p.x][p.y] = 2;
			}
		}
	}

	private static void bfs() {
		
		//맵복사
		int[][] copy=new int[N][M];
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				copy[i][j]=map[i][j];
			}
		}
		
		Deque<Pos> redQ=new ArrayDeque<Pos>();
		Deque<Pos> greenQ=new ArrayDeque<Pos>();
		for(Pos p:red) {
			redQ.offer(p);
		}
		for(Pos p:green) {
			greenQ.offer(p);
		}

		//visit배열
		int[][] visit=new int[N][M];
		int flowerCnt=0;
		int time=1;
		while(true) {
			
			if(redQ.isEmpty() && greenQ.isEmpty()) {
				if(flowerCnt>ans)ans=flowerCnt;
				
				break;
			}
			
			int redSize=redQ.size();
			int greenSize=greenQ.size();
			
			//빨강거 먼저
			while(redSize-->0) {
				Pos p=redQ.poll();
				if(copy[p.x][p.y]==10)continue;
				for(int i=0; i<4; i++) {
					int nx=p.x+dx[i];
					int ny=p.y+dy[i];
					if(nx<0||ny<0||nx>=N||ny>=M ||visit[nx][ny]>0)
						continue;
					if(copy[nx][ny]==1 || copy[nx][ny]==2) {
						//퍼뜨릴수 있으면
						visit[nx][ny]=time;
						copy[nx][ny]=-1;
						redQ.offer(new Pos(nx,ny));
						//overlap.add(new Pos(nx,ny));
					}
				}
			}
			//초록 확산
			while(greenSize-->0) {
				Pos p=greenQ.poll();
				for(int i=0; i<4; i++) {
					int nx=p.x+dx[i];
					int ny=p.y+dy[i];
					if(nx<0||ny<0||nx>=N||ny>=M)
						continue;
					if(copy[nx][ny]==1 || copy[nx][ny]==2) {
						//퍼뜨릴수 있으면
						copy[nx][ny]=-2;
						greenQ.offer(new Pos(nx,ny));
					}
					if(copy[nx][ny]==-1 && visit[nx][ny]==time) {//빨간색이고,같은 턴에 넣은거면
						flowerCnt++;
						copy[nx][ny]=10;
					}
				}
			}
			time++;
		}
	}


}