BOJ18809 Gaaaaaaarden

<문제 요약>

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

18809번: Gaaaaaaaaaarden

1. 배양액은 매 초마다 이전에 배양액이 도달한 적이 없는 인접한 땅으로 퍼져간다
2. 초록색 배양액과 빨간색 배양액이 동일한 시간에 도달한 땅에서는 꽃 -> 꽃이 핀 곳에서는 배양액이 퍼지지 않는다
3. 배양액을 남김없이 사용해야 한다
4. 꽃의 최대 개수를 구하자
5. 입력
N, M, G, R 행, 열, 초록색 배양액, 빨간색 배양액
0, 1, 2 호수, 배양액을 뿌릴 수 없는 땅, 배양액을 뿌릴 수 있는 땅

<풀이 흐름, Source Code>

1. 변수 선언
(1) x,y,color,time 을 변수로 갖는 구조체 선언 pair
(2) pair형의 map 선언
(3) pair형의 list 선언 position
(4) total_time

2. 풀이
(1) map 중 2로 입력되는 곳의 x,y,color,time을 list position에 따로 저장해둔다
(2) list position에서 배양액이 위치할 수 있는 경우를 조합을 통해 다 뽑아낸다
배열 pick에는 3 빈곳, 4 green, 5 red로 표현하고
배양액이 위치할 수있는 곳이 총 5군데이고 green 2, red 1이라고 한다면 아래와 같이 데이터가 나와야 된다
2 2 1 0 0 0
2 2 0 1 0 0
2 2 0 0 1 0
.......
0 0 0 1 2 2
그러면 list position에 위치가 5군데 있을 것이고 0 0 0 1 2 2의 경우 첫번째~세번째까지는 빈곳 네번째 green 5~6번째 red를 위치
한다.

(3) bfs를 돌린다
(3)-1. 호수인 곳은 갈 수 없다 map.color = 0
(3)-2. 꽃인 곳은 갈 수 없다 map.color = 6
(3)-3. 동시간대가 아닌 배양액이 위치한 곳은 갈 수 없다 map.color = 4 or 5 & map.time != total_time
(3)-4. 배열을 벗어나는 곳은 갈수없다
※ map.color가 position.color와 서로 반대되는 배양액이고 동시간대이면 꽃으로 변한다!!

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

public class BOJ18809_Gaaaaaaarden {

	private static class pair {
		int x, y, color, time;

		pair(int x, int y, int color, int time) {
			this.x = x;
			this.y = y;
			this.color = color;
			this.time = time;
		}
	}

	static final int EMPTY = 0, RED = 4, GREEN = 5, FLOWER = 6;
	static pair map[][];
	static pair map_copy[][];
	static boolean visited[][];
	static int pick[];
	static int N, M, G, R, total_time, result = -1;
	static ArrayList<pair> position;
	static Queue<pair> q = new LinkedList<>();
	static int[] dx = { 0, 1, 0, -1 }, dy = { -1, 0, 1, 0 };

	public static void main(String[] args) throws IOException {
		input();
		pick = new int[position.size()];
		combination(pick, R, G, 0);
		System.out.print(result);
	}

	private static void input() throws IOException {
		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 pair[N][M];
		map_copy = new pair[N][M];
		visited = new boolean[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				map[i][j] = new pair(0, 0, 0, 0);
				map_copy[i][j] = new pair(0, 0, 0, 0);
			}
		}
		position = new ArrayList<pair>();
		total_time = 0;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < M; j++) {
				int what = Integer.parseInt(st.nextToken());
				map[i][j].color = what;
				map[i][j].time = 0;
				map_copy[i][j].color = what;
				map_copy[i][j].time = 0;
				if (what == 2) {
					position.add(new pair(i, j, what, 0));
				}
			}
		}
	}

	private static int bfs() {
		int bfs_result = 0;
		for (int i = 0; i < position.size(); i++) {
			if (pick[i] != EMPTY) {
				pair p = position.get(i);
				q.add(new pair(p.x, p.y, pick[i], total_time));
				map[p.x][p.y].color = pick[i];
				visited[p.x][p.y] = true;
			}
		}

		while (!q.isEmpty()) {
			int q_size = q.size();
			total_time++;
			for (int size = 0; size < q_size; size++) {
				pair p = q.poll();
				// 현재칸 체크
				if(map[p.x][p.y].color == FLOWER || map[p.x][p.y].color == 0)
					continue;
				for (int di = 0; di < 4; di++) {
					int nx = p.x + dx[di];
					int ny = p.y + dy[di];
					if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
						if (map[nx][ny].color == 0 || map[nx][ny].color == FLOWER)
							continue;
						else if ((map[nx][ny].color == GREEN || map[nx][ny].color == RED)
								&& map[nx][ny].time != total_time) {
							continue;
						} else if (!visited[nx][ny] && (map[nx][ny].color == 1 || map[nx][ny].color == 2)) {
							visited[nx][ny] = true;
							map[nx][ny].color = p.color;
							map[nx][ny].time = total_time;
							q.add(new pair(nx, ny, p.color, total_time));
						} else if (map[nx][ny].color == RED && map[nx][ny].time == total_time) {
							if (p.color == GREEN) {
								map[nx][ny].color = FLOWER;
								bfs_result++;
							}
						} else if (map[nx][ny].color == GREEN && map[nx][ny].time == total_time) {
							if (p.color == RED) {
								map[nx][ny].color = FLOWER;
								bfs_result++;
							}
						}
					}
				}
			}
		}

		return bfs_result;
	}

	static void combination(int[] pick, int red, int green, int start) {
		if (red == 0 && green == 0) {
			result = Math.max(bfs(), result);
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < M; j++) {
					map[i][j].color = map_copy[i][j].color;
					map[i][j].time = map_copy[i][j].time;
					visited[i][j] = false;
				}
			}
			return;
		}

		for (int i = start; i < pick.length; i++) {
			if (pick[i] == EMPTY) {
				if (red > 0) {
					pick[i] = RED;
					combination(pick, red - 1, green, Math.max(start, i + 1));
					pick[i] = EMPTY;
				}
			}
		}

		for (int i = start; i < pick.length; i++) {
			if (pick[i] == EMPTY) {
				if (green > 0) {
					pick[i] = GREEN;
					combination(pick, red, green - 1, Math.max(start, i + 1));
					pick[i] = EMPTY;
				}
			}
		}
	}
}

 

<문제 Issue>

1. 인접한 칸을 검사하기 전에 현재 칸도 검사해야 된다. 동시간대에 두개의 배양액이 합쳐진 곳은 꽃으로 변하는데 꽃으로 변하기 전 배양액은 이미 큐에 들어간 상태라서 다음에 꺼내서 또 인접한 곳으로 퍼트린다.

0초

G		R

1초 G

G
G	G	R

이때 두개의 G는 큐에 들어간다.

1초 R

G		R
G	GR	R

이때 GR부분은 꽃으로 변하면서 R은 큐에 들어가지 않는다.

2초 G

G	G
G	F	R

1행1열의 G에서 오른쪽으로 퍼지긴 하지만, F에 남아있던 G에 의해 위로 G가 퍼진다. → 현재칸이 꽃이거나 호수면 퍼트리지 않도록 조건 추가

 

<중요 정리>

X