[백준알고리즘] 1014번: 컨닝 -C++

[백준알고리즘] 1014번: 컨닝 -C++

1014번: 컨닝 (acmicpc.net)

1014번: 컨닝

으으음.. 되게 어려웠다.

 

처음에는 단순히 Bruteforce 방식으로 푸는데 DFS를 적용해서 풀었다. 거의 다 풀었다가 생각해보니까 시간 복잡도가 초과한다는 것을 알게 되었다. 사실상 브루트 포스를 푸는 것이기 때문에 \(O(2^(n * m))\)의 시간 복잡도가 걸려 최대 \( 2^{100} = 1,267,650,600,228,229,401,496,703,205,376 \)라는 말도 연산 횟수가 나온다.

 

그래서 끙끙대다가 결국 푸는 방법을 찾았는데, 이전에 사용했던 비트마스크를 사용하는 방법이 있다고 나왔다.

비트 마스크는 이전에 외판원 순회 문제 2를 풀 때 사용한 적이 있었다.

 

비트 마스크.. 동적 계획법... 을 사용하라고는 하는데.. 그래도 감이 잡히지 않아서 다른 분의 코드를 확인하게 됐다. 그리고 똭! 하고 비트 마스크를 사용하는 방법에 대해 다시 깨닫게 되었다.

 

그때 당시 참고햇던 블로그는 여기 링크를 타면 된다.

 

외판원 순회 문제에서 사용했던 비트 마스크 메모이제이션 방법과는 약간 다르게 사용해야 한다. 그 점은 아래 풀이 설명에서 다뤄보도록 하겠다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

문제 풀이에 앞서 다른 분의 코드를 봤다고 했는데, 그분의 풀이는 아래 블로그에 포스팅되어있다.

[BOJ] 백준 1014번: 컨닝 (tistory.com)

[BOJ] 백준 1014번: 컨닝

이분의 풀이를 이해하고 나도 새롭게 풀었더니 통과하고 나서 보니까 사실상 리팩토링 수준인 것 같기도 하다^~^..

그래도 나름 쉽게 설명했으니, 읽어보도록 하자!

 

---

 

풀이

이제 문제의 요구조건을 확인해보자.

컨닝 가능 범위

1. 교실의 크기가 주어진다.
2. 학생이 \((i, j)\)에 앉아있다면, \( D ( i, j - 1) \), \( E ( i , j + 1 ) \), \( A ( i -  1, j - 1) \), \( C ( i - 1, j + 1) \) 4 자리는 컨닝이 가능하기 때문에 학생이 앉으면 안 된다.
   • 확장해서 생각해보면 이것은 \( (i, j) \)에 앉아있는 학생이 컨닝 가능한 자리이며, \( ( i, j ) \) 학생이 컨닝을 당할 수 있는 자리인 \( ( i + 1, j - 1) \)와 \( (i + 1, j + 1) \)도 학생은 앉지 못해야 한다.
3. 모든 학생들이 컨닝을 못 하도록 자리배치를 해야 하며, 가장 많은 학생을 배치한 경우의 학생의 수를 구한다.

 

딱 보더라도 요구 조건 2번 때문에 문제가 어려워진다..

 

2번을 풀기 위해서 코드에서는 dfs 함수와 dp 함수로 나눠서 자리배치를 해결했다.

각각의 역할은 다음과 같다.

 

dfs 함수

• 교실의 크기에서 열의 개수(가로길이 \(M\))가 주어졌을 때 학생이 앉을 수 있는 자리배치를 구한다.
• 이때 앞 줄과 뒷 줄을 생각하지 않고, 부서진 책상도 고려하지 않으며, 그저 한 줄에 앉을 수 있는 학생의 배치를 구한다.
• 이 과정을 DFS 과정을 통해 구해낸다.
• 한 줄에 앉을 수 있는 학생 배치의 모든 경우의 수를 vector로 저장한다.

 

dp 함수

먼저, 이 함수에서 bitMask 배열을 사용하는데, bitMask가 무엇인지 확인부터 하고 설명을 하겠다.

$$bitMask[current\_line\_number][before\_line\_bitmask] = \\ 현재\ line을\ 포함한\ 뒷자리에\ 학생들이\ 앉는\ 최대\ 학생수$$

 

• bitMask 배열을 사용해 비트 마스크 메모이제이션을 사용한다.
  • 각 줄에 배치할 수 있는 학생의 위치는, 바로 앞 줄의 학생 배치에만 영향을 받기 때문이다.
• 현재 줄의 bitMask를 생성할 때 dfs 함수를 통해 만든 한 줄에 앉을 수 있는 학생의 배치에 따라서 앉힌다.
• 현재 줄에 앉는 각각의 학생의 배치에 따라서 다음 뒷 줄부터 최대로 앉을 수 있는 학생의 수를 확인하고, 현재 \(bitMask [lineNumber] [beforeBits]\)에 저장한다.

 

이렇게 dfs 함수와 dp 함수를 각각 재귀를 통해 구하게 된다면, 기존의 모든 경우를 확인하는 Bruteforce에 비해 효과적으로 시간을 줄일 수 있다.

 

---

 

기존에 사용했던 비트 마스크를 사용한 다이나믹 프로그램은 현재 노드까지 사용된 노드에 대한 비트와 현재 노드에 대한 정보로 이후 경로에 대한 결과값을 저장하는 메모이제이션 역할을 수행헀다.

 

여기서는 바로 앞줄의 상태만 저장하면서 재귀적으로 다음 줄, 그다음 줄.... 이런 식의 최대 결과값들을 계속해서 넘겨받으며 갱신했다.

 

그렇기 때문에 비트 마스크를 활용한 다이나믹 프로그래밍을 하면 가능하다고 했을 때 쉽게 접근하지 못한 것 같다.

 

오랜만에 하는 만큼 하루빨리 응용력을 더 키우도록 해야겠다.

 

아래는 위의 풀이 방법대로 푼 C++ 코드다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int bitMask[10][1 << 10];
char board[10][10];

void dfs(const int index, std::string& line);
void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	

	int testCase;
	std::cin >> testCase;
	for (int t = 0; t < testCase; t++)
		solve();
}

void dfs(std::vector<std::string>& lines, int (& dfsArray)[10], int index, int& m)
{
	if (m == index)
	{
		std::string str;
		for (int a : dfsArray)
			str += std::to_string(a);
		
		lines.push_back(str);
		return;
	}
	
	dfsArray[index] = 0;
	dfs(lines, dfsArray, index + 1, m);

	if (0 < index && dfsArray[index - 1] != 0)
		return;

	dfsArray[index] = 1;
	dfs(lines, dfsArray, index + 1, m);
}

int dp(std::vector<std::string>& lines, int lineNumber, int beforeBits, int& n, int& m)
{
	if (n == lineNumber)
		return 0;

	if (-1 < bitMask[lineNumber][beforeBits])
		return bitMask[lineNumber][beforeBits];

	int answer = 0;
	for (auto line : lines)
	{
		int bits = 0;
		int count = 0;

		for (int i = 0; i < m; i++)
		{
			if ('0' == line[i])
				continue;

			if ('x' == board[lineNumber][i])
				continue;

			if (0 < i && beforeBits & (1 << (i - 1)))
				continue;
			
			if (i < m && beforeBits & (1 << (i + 1)))
				continue;

			count++;
			bits |= (1 << i);
		}

		answer = std::max(answer, dp(lines, lineNumber + 1, bits, n, m) + count);
	}

	bitMask[lineNumber][beforeBits] = answer;
	return answer;
}

void solve(void)
{
	std::fill(bitMask[0], bitMask[0] + (10 * (1 << 10)), -1);
	std::fill(board[0], board[0] + (10 * 10), 0);

	int n, m;
	std::cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			std::cin >> board[i][j];

	int dfsArray[10];
	std::vector<std::string> lines;
	dfs(lines, dfsArray, 0, m);

	std::cout << dp(lines, 0, 0, n, m) << '\n';
}