백준 18809번 - Gaaaaaaaaaarden

문제 설명

• https://www.acmicpc.net/problem/18809
• 땅은 배양액을 뿌리지도, 전파되지도 못하는 곳(호수), 배양액을 뿌릴 수 있는곳, 배양액은 뿌릴 수 없지만 전파될 수는 있는 곳 으로 나눠져 있습니다.
• 배양액은 매 초 동시에 인접한 곳으로 전파됩니다.
  • 호수로는 전파되지 못합니다.
  • 이미 꽃이 핀 곳으로는 전파되지 못합니다.
• 두 배양액이 동시간에 특정 땅에 도달하면 그 땅에는 꽃이 핍니다.
• 배양액은 반드시 모두 사용해야 합니다.

접근법

• 배양액을 놓을 수 있는 모든 경우의 수를 다 계산해보는 방식으로 진행했습니다.
• 배양액을 놓기 위해서 조합을 사용했습니다. 이때 2개의 조합을 사용했습니다.
  • 첫 번째는 배양액을 놓을 수 있는 땅을 선정하는 조합입니다.
  • 두 번째는 첫번째에서 선택된 땅에서 초록색 배양액과 빨간색 배양액의 위치를 고르는 조합입니다.

정답

import java.util.*;

import java.io.*;
import java.math.*;

public class Main {
	static int[] dx = {0,1,0,-1};
	static int[] dy = {1,0,-1,0};
	static int maxVal = Integer.MIN_VALUE;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int G = Integer.parseInt(st.nextToken());
		int R = Integer.parseInt(st.nextToken());
		int[][] board = new int[N][M];
		List<int[]> candi = new LinkedList<int[]>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine()," ");
			for (int j = 0; j < M; j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				if(board[i][j] == 2) {
					candi.add(new int[] {i,j});
				}
			}
		}
		comb(0,0,G,R,candi.size(),new boolean[candi.size()],candi,new int[G+R][2],board);
		System.out.println(maxVal);
		
	}
	// 배양액을 놓을 수 있는 땅들 중 G+R개를 고릅니다.
	public static void comb(int depth, int start, int G, int R, int maxSize, boolean[] v, List<int[]> candi,int[][] answer,int[][] board) {
		if(depth == G+R) {
			comb2(0,0,G,G+R,new boolean[G+R],answer,board);
			return;
		}
		
		for (int i = start; i < maxSize; i++) {
			if(v[i]) continue;
			v[i] = true;
			answer[depth] = candi.get(i);
			comb(depth+1,i+1,G,R,maxSize,v,candi,answer,board);
			v[i] = false;
		}
		
	};
	
    // G+R개의 위치 중 G개를 선택합니다.
	public static void comb2(int depth, int start, int size, int maxSize, boolean[] v, int[][] answer,int[][] board) {
		if(depth == size) {
			func(answer,v,board);
			return;
		}
		
		for (int i = start; i < maxSize; i++) {
			if(v[i]) continue;
			v[i] = true;
			comb2(depth+1,start+1,size,maxSize,v,answer,board); // i+1이 아닌 start+1로 잘못 적음 -> 자세한 내용은 아래 기타에 적었습니다.
			v[i] = false;			
		}
	}
	
    // 선택된 땅으로 초기값 설정을 한 뒤 queue에 넣고 BFS를 실행합니다. 
	public static void func(int[][] answer, boolean[] v,int[][] board) {
		LinkedList<int[]> q = new LinkedList<int[]>();
		Info[][] newBoard = new Info[board.length][board[0].length];
		for (int i = 0; i < v.length; i++) {
			if(v[i]) {
				newBoard[answer[i][0]][answer[i][1]] = new Info(0,1);
				q.add(new int[] {answer[i][0],answer[i][1],1});
			}else {
				newBoard[answer[i][0]][answer[i][1]] = new Info(0,2);
				q.add(new int[] {answer[i][0],answer[i][1],2});
			}
		}
		BFS(q,newBoard,board);
	}
	
	public static void BFS(LinkedList<int[]> q, Info[][] newBoard, int[][] board) {
		int answer = 0;
		int time = 0;
		while(!q.isEmpty()) {
			int size = q.size();
			time++; // 초기값의 time이 0이기 때문에 처음부터 1을 더해줘야 합니다.
			while(--size>=0) {
				int[] now = q.poll();
				if(newBoard[now[0]][now[1]].color == -1) continue;
				for (int d = 0; d < 4; d++) {
					int nx = now[0]+dx[d];
					int ny = now[1]+dy[d];
					if(0 <= nx && nx < newBoard.length && 0 <= ny && ny < newBoard[0].length && board[nx][ny] != 0) { // 호수가 아님
						if(newBoard[nx][ny] != null && newBoard[nx][ny].color != -1 && now[2] != newBoard[nx][ny].color && time == newBoard[nx][ny].time) { // 꽃이 핌
							newBoard[nx][ny] = new Info(time,-1);
							answer++;
						}else if(newBoard[nx][ny] == null) { // 아무런 배양액이 없는 땅
							newBoard[nx][ny] = new Info(time,now[2]);
							q.add(new int[] {nx,ny,now[2]});
						}
					}
				}
			}	
		}

		maxVal = Math.max(maxVal, answer);
	}
	public static class Info{
		int time;
		int color;
		public Info(int time, int color) {
			super();
			this.time = time;
			this.color = color;
		}
		@Override
		public String toString() {
			return "Info [time=" + time + ", color=" + color + "]";
		}
		
		
	}
}

기타

• 계속해서 시간초과가 났습니다. 50x50 반례(https://www.acmicpc.net/board/view/88389)를 실행했을 때 별로 금방 결과가 나와 시간소모가 크지 않다고 생각했는데 뭐가 문제였는지 잘 모르겠습니다.
• 어쩌다가 java8을 java11로 바꿔봤는데 겨우 통과했습니다. 사실상 틀린거와 다름없다고 생각합니다. 시간복잡도를 줄이는 방법을 조금 더 공부해야 할 거 같습니다.
  
• N+G개에서 G개를 선택하는 comb2를 조합이 아니라 부분집합방식으로 변경하니 시간이 개선됐습니다.

수정 전

	public static void comb2(int depth, int start, int size, int maxSize, boolean[] v, int[][] answer,int[][] board) {
		if(depth == size) {
			func(answer,v,board);
			return;
		}
		
		for (int i = start; i < maxSize; i++) {
			if(v[i]) continue;
			v[i] = true;
			comb2(depth+1,start+1,size,maxSize,v,answer,board);
			v[i] = false;			
		}
	}

수정 후

	public static void comb2(int depth,int selectedNumCnt, int size, int maxSize, boolean[] v, int[][] answer,int[][] board) {
		if(selectedNumCnt == size) {
			func(answer,v,board);
			return;
		}
		if(depth == maxSize) return;
		v[depth] = true;
		comb2(depth+1,selectedNumCnt+1,size,maxSize,v,answer,board);
		v[depth] = false;
		comb2(depth+1,selectedNumCnt,size,maxSize,v,answer,board);
	}

• 알고보니 조합과 부분집합의 차이가 아니라 조합을 잘못 구현해 발생한 문제였습니다.
  start+1이 아니라 i+1을 넘겨야 되는데 실수했었습니다.

	public static void comb2(int depth, int start, int size, int maxSize, boolean[] v, int[][] answer,int[][] board) {
		if(depth == size) {
			func(answer,v,board);
			return;
		}
		
		for (int i = start; i < maxSize; i++) {
			if(v[i]) continue;
			v[i] = true;
			comb2(depth+1,i+1,size,maxSize,v,answer,board); // start+1이 아닌 i+1
			v[i] = false;			
		}
	}