백준 18809 Gaaaaarden

 

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

18809번: Gaaaaaaaaaarden

전형적인 삼성 역량테스트에서 나올법한 문제

 

너무 친절하게 테스트케이스를 다 줘서 생각보다 쉽게 풀었던 문제이다.

 

삼성 역테 준비하는 사람이면 시간 맞춰놓고 1시간안에 풀기 연습 하면 괜찮을듯

 

※ 풀이과정

1. 땅의 조합 찾기(DFS)

 

n : 땅갯수 g : 초록색 갯수 r : 빨간색 갯수

1) 초록색 배양할 땅고르기 (DFS) nCg

2) 빨간색 배양할 땅고르기 (DFS) n-gCr

3) 전체 가짓수 nCg * n-gCr 

 

여기서 주의할 점은 n>=(g+r)이라는 점 즉 조합을 2번에 걸쳐서 구해야한다.

 

2. 시뮬레이션 돌리기(BFS)

1) 앞의 1번에서 구한 조합으로 시뮬레이션을 돌리고 시뮬레이션 한 값의 최대값을 구한다.

2) 당연히 map 값이 1이거나 2인 지점만 방문가능하다. (호수인 지점이나 초록색 빨간색이 이미 그전에 뿌려진 점도 방문불가능)

3) 주의할점은 초록색과 빨간색이 "동시에 만나는 지점에서만 꽃이 핀다는점" 나 같은경우에는 초록색을 먼저 bfs 돌리고 방문 가능한점들을 map의 값을 -1로 바꿨고, 그 후 빨간색에서 BFS을 돌렸을때 map의 값이 -1인 지점을 방문하면 꽃이 핀다고 카운트 했음(당연히 카운트하자마자 -1을 다른값으로 바꿔야된다 아니면 중복되서 카운트 된다.)

 

package 백준;

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

public class Garden {
	static class MyScanner {
		BufferedReader bf;
		StringTokenizer st;

		MyScanner() {

			bf = new BufferedReader(new InputStreamReader(System.in));

		}

		String next() {

			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (Exception e) {
					e.printStackTrace();
				}

			}
			return st.nextToken();

		}

		int nextInt() {
			return Integer.parseInt(next());

		}

	}

	static int N, M, G, R;
	static int map[][];
	static int answer = 0;
	static Point gal[];
	static Point ral[];
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };

	static class Point {
		int x;
		int y;
		char color;
		int time;

		Point(int x, int y, char val, int time) {
			this.x = x;
			this.y = y;
			this.color = val;
			this.time = time;
		}
	}

	static void rspread(int idx, int rcnt) {

		if (rcnt < R) {
			for (int i = idx; i < pc; i++) {
				if (map[pland[i].x][pland[i].y] != 2)
					continue;
				map[pland[i].x][pland[i].y] = 4;
				rspread(i + 1, rcnt + 1);
				map[pland[i].x][pland[i].y] = 2;
			}
		} else {
			int partial_answer = bfs();

			ddd++;
			answer = Math.max(answer, partial_answer);
			return;
		}
	}

	static void gspread(int idx, int gcnt) {

		if (gcnt < G) {
			for (int i = idx; i < pc; i++) {
				map[pland[i].x][pland[i].y] = 3;
				gspread(i + 1, gcnt + 1);
				map[pland[i].x][pland[i].y] = 2;

			}
		} else {

			ccc++;
			rspread(0, 0);

		}

	}

	static void print_map(int map[][]) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.printf(map[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println();
	}

	static Point pland[];
	static int pc;
	static int ddd;
	static int ccc;
	
	static int bfs() {

		Queue<Point> gq = new LinkedList<Point>();
		Queue<Point> rq = new LinkedList<Point>();
		int pa = 0;
		int temp[][] = new int[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				temp[i][j] = map[i][j];
			}
		}
	
		for (int i = 0; i < pc; i++) {
			if (temp[pland[i].x][pland[i].y] == 3)
				gq.add(new Point(pland[i].x, pland[i].y, 'g', 0));// 초록색 큐
			if (temp[pland[i].x][pland[i].y] == 4)
				rq.add(new Point(pland[i].x, pland[i].y, 'r', 0));// 빨간색 큐
		}

		while (!gq.isEmpty() || !rq.isEmpty()) {

			int gs = gq.size();
			int rs = rq.size();
			ArrayList<Point> tq = new ArrayList<Point>();
			for (int i = 0; i < gs; i++) {

				Point g = gq.poll();
				for (int j = 0; j < 4; j++) {
					int nx = g.x + dx[j];
					int ny = g.y + dy[j];
					int nt = g.time + 1;
					if (nx < 0 || ny < 0 || nx >= N || ny >= M)
						continue;

					if (temp[nx][ny] != 1 && temp[nx][ny] != 2)
						continue;
					tq.add(new Point(nx, ny, 'g', nt));
					temp[nx][ny] = -1; // g가 퍼진땅 동시 체크 위함
				}
			}
			for (int i = 0; i < rs; i++) {

				Point r = rq.poll();
				for (int j = 0; j < 4; j++) {
					int nx = r.x + dx[j];
					int ny = r.y + dy[j];
					int nt = r.time + 1;
					if (nx < 0 || ny < 0 || nx >= N || ny >= M)
						continue;
					if (temp[nx][ny] == -1) {
						temp[nx][ny] = 7; // g가 퍼진땅 동시 체크 위함
						pa++;
					}
					if (temp[nx][ny] != 1 && temp[nx][ny] != 2)
						continue;
					temp[nx][ny] = -2; // g가 퍼진땅 동시 체크 위함
					tq.add(new Point(nx, ny, 'r', nt));

				}
			}
			for (Point p : tq) {
				if (temp[p.x][p.y] == -1) {
					temp[p.x][p.y] = 3;
					gq.add(p);
				}
				if (temp[p.x][p.y] == -2) {
					temp[p.x][p.y] = 4;
					rq.add(p);d
				}

			}

		}

		return pa;
	}

	public static void main(String[] args) {
		MyScanner sc = new MyScanner();
		N = sc.nextInt();
		M = sc.nextInt();
		G = sc.nextInt();
		R = sc.nextInt();

		map = new int[N][M];
		pland = new Point[11];
		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = sc.nextInt();
				if (map[i][j] == 2) {
					pland[pc++] = new Point(i, j, 'p', 0);
				}
			}
		}
		gal = new Point[G];
		ral = new Point[R];
		gspread(0, 0);

		System.out.println(answer);
	}

}