[백준] 18809.Gaaaaaaaaaarden / BFS, 조합

@BFS, 조합 / 1h 16m (필기 12m, 디버깅 29m)

다 풀었는데 계속 틀리게 나와서 뭔가 했더니, 조건을 하나 빼먹었었다.

그런데 예전 풀이내역 보니 그때도 똑같이 이걸로 시간을 썼었음.. ㅜㅜ

같은 실수 반복하지 않기!

 

근데 골드 1 치고는 쉽다. 난이도가 조금 후하게 붙은 것 같기도..

 

문제 링크

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

18809번: Gaaaaaaaaaarden

 

구현 방법

1. 값이 2인 칸(== 배양액을 뿌릴 수 있는 칸)을 전부 ArrayList에 넣는다

2. ArrayList의 size 개수 중에서 G개, R개를 각각 조합으로 선택한다.

3. bfs를 도는데 이때 단순히 while문으로만 돌리는 것이 아니라,

한번 퍼질 때의 시간이 중요하므로 매번 queue.size()개수를 별도의 변수로 담아놓고 그 size만큼 돌린다 (이게 한 턴임)

4. 초록색을 먼저 한 턴만큼 퍼뜨리고, 그 다음 빨간색을 퍼뜨리면서

빨간색이 퍼져나가려는 칸에 이미 다른 배양액이 있을 때, 같은 시간에 퍼진 것이면서 && 다른 색상인지를 확인한다.

 

 

삽질 포인트

구현할 때 초록색을 먼저 퍼뜨리고, 이후 빨간색을 퍼뜨리면서

빨간색이 가려는 칸에 초록색이 있으면 count++ 해주는 방식으로 진행했다.

그런데 문제는 이렇게 되면 이전에 Queue에 넣어놓은 초록색은 여전히 살아있어서 다음 턴에 또 퍼지게 된다.

 

그래서 이를 막기 위해 초록색이 퍼지기 전에, 현재 자신의 칸이 비어있으면 continue하게끔 조건을 추가했다.

 

 

코드

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

public class Main {
	
	static class Node {
		int x, y, time, color;
		
		Node (int x, int y) {
			this.x = x;
			this.y = y;
		}
		
		Node (int x, int y, int time, int color) {
			this(x, y);
			this.time = time;
			this.color = color;
		}	
	}
	
	static int N, M, G, R, gcombi[], rcombi[], map[][], copyMap[][], colorMap[][], SIZE, count, max = 0;
	static boolean check[];
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1};
	static ArrayList<Node> enableList = new ArrayList<Node>();
	static Queue<Node> greenQ = new LinkedList<Node>();
	static Queue<Node> redQ = new LinkedList<Node>();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		G = stoi(st.nextToken());
		R = stoi(st.nextToken());
		
		gcombi = new int[G];
		rcombi = new int[R];
		map = new int[N][M];
		copyMap = new int[N][M];
		colorMap = 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] = stoi(st.nextToken());
				if (map[i][j] == 2)
					enableList.add(new Node(i, j));
				
				switch (map[i][j]) {
				case 0: map[i][j] = -1;	break;
				case 1: map[i][j] = -2;	break;
				case 2: map[i][j] = -3;	break;
				}
			}
		}
		SIZE = enableList.size();
		check = new boolean[SIZE];
		greenCombi(G, 0, 0);
		System.out.println(max);
	}

	private static void greenCombi(int n, int k, int idx) {
		if (n == k) {
			redCombi(R, 0, 0);
			return;
		}
		
		for (int i = idx; i < SIZE; i++) {
			if (check[i]) continue;
			check[i] = true;
			gcombi[k] = i;
			greenCombi(n, k + 1, i + 1);
			check[i] = false;
		}
	}

	private static void redCombi(int n, int k, int idx) {
		if (n == k) {
			count = 0;
			copyMapMake();
			bfs();
			if (max < count) max = count;
			
			return;
		}
		for (int i = idx; i < SIZE; i++) {
			if (check[i]) continue;
			check[i] = true;
			rcombi[k] = i;
			redCombi(n, k + 1, i + 1);
			check[i] = false;
		}
	}

	private static void bfs() {
		while (!greenQ.isEmpty()) {
			int gsize = greenQ.size();
			for (int i = 0; i < gsize; i++) {
				Node temp = greenQ.poll();
				
				if (copyMap[temp.x][temp.y] == -1) continue;
				
				for (int d = 0; d < 4; d++) {
					int nx = temp.x + dx[d];
					int ny = temp.y + dy[d];
					
					if (nx < 0 || nx >= N || ny < 0 || ny >= M || copyMap[nx][ny] >= -1)
						continue;
					
					copyMap[nx][ny] = temp.time;
					colorMap[nx][ny] = 3;
					greenQ.add(new Node(nx, ny, temp.time + 1, temp.color));
				}
			}
			
			int rsize = redQ.size();
			for (int i = 0; i < rsize; i++) {
				Node temp = redQ.poll();
				for (int d = 0; d < 4; d++) {
					int nx = temp.x + dx[d];
					int ny = temp.y + dy[d];
					
					if (nx < 0 || nx >= N || ny < 0 || ny >= M || copyMap[nx][ny] == -1)
						continue;
					
					if (copyMap[nx][ny] < -1) {
						copyMap[nx][ny] = temp.time;
						colorMap[nx][ny] = 4;
						redQ.add(new Node(nx, ny, temp.time + 1, temp.color));
						
					} else {
						if (copyMap[nx][ny] == temp.time && colorMap[nx][ny] == 3) {
							count++;
							copyMap[nx][ny] = -1;	//괜찮은가..?
							colorMap[nx][ny] = 0;
						}
					}
				}
			}
		}
	}

	private static void copyMapMake() {
		for (int i = 0; i < N; i++) {
			copyMap[i] = map[i].clone();
			Arrays.fill(colorMap[i], 0);
		}
		
		greenQ.clear();
		for (int i = 0; i < G; i++) {
			Node temp = enableList.get(gcombi[i]);
			copyMap[temp.x][temp.y] = 0;
			colorMap[temp.x][temp.y] = 3;
			greenQ.add(new Node(temp.x, temp.y, 1, 3));
		}
		
		redQ.clear();
		for (int i = 0; i < R; i++) {
			Node temp = enableList.get(rcombi[i]);
			copyMap[temp.x][temp.y] = 0;
			colorMap[temp.x][temp.y] = 4;
			redQ.add(new Node(temp.x, temp.y, 1, 4));
		}
	}

	private static int stoi(String str) {
		return Integer.parseInt(str);
	}
}

 

 

왜 지난번보다 더 느려졌지..ㅎㅎ

여튼 무난한 문제였다. 재밌게 풀었음

끝!