백준 18809 <Gaaaaaaaaaarden>

씨앗을 놓을 수 있는 위치를 조합으로 구한 다음 씨앗을 퍼트려 꽃의 개수를 구하는 시뮬레이션 문제이다.

 

많은 시간을 들이면 풀 수 있는 문제기 때문에 빠른시간내에 방법을 생각하고 예외사항을 처리하는 게 문제였다.

 

문제를 해결하면서 고려해야 할 점은 두가지가 있다.

1. 조합을 이용해 두가지 씨앗의 종류를 겹치지 않게 선택하는 방법
2. 씨앗을 퍼트리면서 다른종류의 씨앗이 다음 차례에 동시에 위치하게 되면 꽃이 피게 되고 진행하지 않는 것 

2번 부분을 처리하는게 가장 힘이 들었는데 두 개의 씨앗이 동시에 마주치는 경우를 처리해주는 방법이 어려웠다.

 

기본적으로 씨앗의 종류와 위치를 나타내기위한 클래스를 선언했다.

이후에는 씨앗을 놓을수 있는 장소만 배열에 넣기 위해 

2인 위치를 ArrayList배열에 담아서 나타냈다.

 

go함수를 이용해서 조합을 고르는 방법을 나타냈다.

 

기본적으로 k는 총 고른 씨앗의 수를 나타내고 start는 ArrayList에 담은 씨앗의 위치를 나타냈다.

 

num[1]에는 초록씨앗의 수를 담고 num [2]에는 빨간 씨앗의 수를 담아서 중복이 되지 않도록 조합을 나타냈다.

 

예를 들어

 

 

이렇게 같은 위치에 같은 씨앗이 오지 않기 때문에 여러 조합을 구할 수 있게 된다.

 

모든 씨앗을 사용하지 않으면 안되기 때문에 k가 씨앗의 개수만큼 차게 되면 BFS를 하게 되고 꽃을 피우는 개수를 구하게 된다.

 

 

 

BFS함수를 구성하는데 가장 애를 먹은 문제 였다. 

 

 

큐를 다 퍼티리고 나면 새로운 맵을 구성 해 퍼트린 것을 표시하고 큐에 담고 하려고 했지만 맵의 크기가 최대 2500이기 때문에 시간 초과가 나지 않을까 하는 생각에 다른 방법을 고려했다.

 

다음 생각 했던 방법은 이동한 장소에 visit배열을 이용해 바로 자신의 씨앗을 퍼트리고 다음 씨앗을 퍼트리는 방법을 하려고 했는데 

이러한 문제가 생긴다는 것을 알게 되었고

 

큐를 두개 사용하면서 하루가 지나면 그 지점을 가신의 씨앗으로 퍼트리는 큐,  하루가 지나기 전에는 자신이 이동할 수 있는 지점을 -1로 표시하도록 했다.

 

이 부분에서 또한 중요한 부분은 자신이 한칸을 이동할 수 있으면 그 지점에서 4방향을 탐색해 자신과 다른 씨앗이 있으면 꽃이 필수 있다고 체크를 하는 것이 중요하다. 

 

전체 코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	public static class Tldkt {
		int x;
		int y;
		int who;

		public Tldkt(int x, int y, int who) {
			this.x = x;
			this.y = y;
			this.who = who;
		}

	}

	static int map[][], n, m, g, r,visit[][],dir[][]= {{-1,0},{0,1},{1,0},{0,-1}},count,max;
	static int num[];
	static ArrayList<Point> a;
	static Tldkt xi[];

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader kb = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(kb.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		g = Integer.parseInt(st.nextToken());
		r = Integer.parseInt(st.nextToken());
		a = new ArrayList<Point>();
		map = new int[n][m];
		num = new int[3];
		
		num[1] = g;
		num[2] = r;
		xi = new Tldkt[g + r];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(kb.readLine());
			for (int j = 0; j < m; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if (map[i][j] == 2) {
					a.add(new Point(i, j));// 씨앗 뿌릴수 있는 위치 담음
				}
			}
		}
		go(0, 0);
		System.out.println(max);
	}

	public static void go(int k, int start) {
		if (k == xi.length) {
			visit=new int[n][m];
			bfs();
			max=Math.max(max, count);
			count=0;
			return;
		}
		for (int i = start; i < a.size(); i++) {
			for (int j = 1; j < 3; j++) {// 1은 초록 2은 빨강
				if (num[j] > 0) {
					xi[k] = new Tldkt(a.get(i).x, a.get(i).y, j);
					num[j]--;
					go(k + 1, i + 1);
					num[j]++;
				}
			}
		}
	}
	public static void bfs() {
		Queue<Tldkt> q=new LinkedList<Tldkt>();
		for(int i=0;i<xi.length;i++) {
			q.add(xi[i]);
		}
		while(!q.isEmpty()) {
			Queue<Tldkt> q2=new LinkedList<Tldkt>();
			while(!q.isEmpty()) {
				Tldkt next=q.remove();
				q2.add(next);
			}
			while(!q2.isEmpty()) {
				Tldkt T=q2.remove();
				for(int j=0;j<4;j++) {
					int x1=T.x+dir[j][0];
					int y1=T.y+dir[j][1];
					if(x1>=0&&x1<n&&y1>=0&&y1<m&&visit[x1][y1]==0&&map[x1][y1]!=0) {
						visit[x1][y1]=T.who;
						boolean flag=false;
						for(int k=0;k<4;k++) {
							int xnext=x1+dir[k][0];
							int ynext=y1+dir[k][1];
							if(xnext>=0&&xnext<n&&ynext>=0&&ynext<m&&visit[xnext][ynext]!=0
                               &&Math.abs(visit[T.x][T.y]-visit[xnext][ynext])==1) {
								count++;
								flag=true;
								break;
							}
						}
						if(!flag)
							q.add(new Tldkt (x1,y1,T.who));
					}
				}
			}
		}
	}

}