[백준 1014번][Java] 컨닝 - 비트마스킹, DP, 메모이제이션

www.acmicpc.net/problem/1014

1014번: 컨닝

 

한달 전인가? 너무 어려워서 패스했던 문제였습니다. 그런데 지금은 풀리네요. 풀이가 보였습니다. (오오... 성장해버렸구나)

 

저는 DP와 비트마스킹을 이용해 풀었습니다. 

 

DP 문제를 풀 때 역시 가장 중요한 건 부분 문제를 정의하는 겁니다.

 

arrageStudent(i, previousRowStatus) : 0 ~ i번째 영역에서 이전 행의 상태가 previousRowStatus 일 때 배치할 수 있는 최대 학생 수

  

위처럼 정의할 수 있겠네요.

최적 부분 구조를 구성하기 위해서는 이전 행의 상태를 포함해야 합니다.

이전 행의 학생 배열 상태가 다음 행의 부분 문제에 영향을 주기 때문인데요. 메모리 제한을 넘지 않는다면 이런 경우에는 부분 문제 정의에 배열 상태와 같은 정보를 포함함으로서 해결할 수 있습니다. 

 

풀이 방법은 현재 행에서 가능한 배치를 모두 찾고 추가된 학생 수를 더해주면서 다음 행으로 재귀 호출합니다. 

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

import static java.lang.Math.max;

public class Main {
	static int T,N,M;
	static char[][] room;
	static int[][] cache;
	public static void main(String[] args) throws IOException {
		InputReader reader = new InputReader();
//		InputReader reader = new InputReader("testcase.txt");
		T = reader.readInt();
		for (int tc = 0; tc < T; tc++) {
			//입력
			StringTokenizer st = new StringTokenizer(reader.readLine());
			N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken());
			room = new char[N][M];
			for (int i = 0; i < N; i++) {
				String rowLine = reader.readLine();
				for (int j = 0; j < M; j++) {
					room[i][j] = rowLine.charAt(j);
				}
			}
			cache = new int[N][1 << M];
			for (int i = 0; i < N; i++) {
				Arrays.fill(cache[i], -1);
			}
			int ret = arrangeMaxStudent(0,0);
			System.out.println(ret);
		}
	}
	/*
	0 ~ rowNum 번째 행까지의 영역에서 이전 행의 상태가 previousState일 때 배치할 수 있는 최대 학생 수
	 */
	private static int arrangeMaxStudent(int rowNum, int previousState) {
		if(rowNum == N) return 0;
		if(cache[rowNum][previousState] != -1) return cache[rowNum][previousState];
		//현재 행에서 가능한 모든 배치를 찾는다.
		List<Integer> currentArrangement = arrangeOneRow(rowNum, previousState);
		int ret = 0;
		for (int i = 0; i < currentArrangement.size(); i++) {
			int currentState = currentArrangement.get(i);
			int addStudents = getStudentAmount(currentState);
			ret = max(arrangeMaxStudent(rowNum+1, currentState)+addStudents, ret);
		}

		return cache[rowNum][previousState] = ret;
	}

	private static List<Integer> arrangeOneRow(int rowNum, int previousState) {
		List<Integer> l = new ArrayList<>();
		findArrangement(rowNum,0,0,previousState,l);
		return l;
	}

	private static void findArrangement(int currentRow, int currentCol, int currentState, int previousState, List<Integer> l) {
		if(currentCol == M) {
			l.add(currentState);
			return;
		}

		if(room[currentRow][currentCol] == '.' && canSeat(currentCol,currentState,previousState)) {
			//앉는 경우
			findArrangement(currentRow, currentCol+1, currentState | (1 << currentCol), previousState, l);
		}
		//앉지 않는 경
		findArrangement(currentRow, currentCol+1, currentState, previousState, l);
	}

	private static boolean canSeat(int index, int currentState, int previousState) {
		boolean leftSideCondition = (previousState & (1 << index-1)) == 0 && (currentState & (1 << index-1)) == 0;
		boolean leftBorderCondition = (previousState & (1 << 1)) == 0 && (currentState & (1 << 1)) == 0;
		boolean rightSideCondition = (previousState & (1 << index+1)) == 0 && (currentState & (1 << index+1)) == 0;
		boolean rightBorderCondition = (previousState & (1 << M-2)) == 0 && (currentState & (1 << M-2)) == 0;
		if(index == 0) return leftBorderCondition;
		if(index == M-1) return rightBorderCondition;

		if(leftSideCondition && rightSideCondition) return true;
		return false;
	}

	private static int getStudentAmount(int currentState) {
		int amount = 0;
		for (int i = 0; i < M; i++) {
			if((currentState & (1<<i)) != 0) amount++;
		}
		return amount;
	}

}
class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public List<Character> readLineIntoCharList() throws IOException {
		List<Character> l = new ArrayList<>();
		while(true) {
			int readVal = br.read();
			if(readVal == '\n' || readVal == -1) break;
			l.add((char)readVal);
		}
		return l;
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}