[백준] 14712: 넴모넴모 (Easy)

문제 링크

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

접근 방식 / 풀이

이 문제는 최대 25개의 칸을 가진 격자판에 '넴모'를 넣었을 때, '넴모'가 올라간 칸이 2 * 2 의 사각형이 만들어지지 않는 경우의 수를 세는 문제이다.
칸 수의 제한이 크지 않기에 모든 경우를 다 생각해볼 수 있을텐데, 브루트포스적으로 모든 경우를 만든 다음에 체크하게 되면, 해당 격자판을 두 번 순환해야 한다; (만들 때, 체크할 때)

따라서 이보다, 백트래킹을 사용해서 조건을 따져가며 경우를 확인하는 것이 올바른 판단이라고 할 수 있다.

격자판의 한 칸을 채우는 recur(int times)이라는 함수를 작성하고, 이 함수의 인자가 $N \times M$ 이 된다면, 조건에 맞게 $N \times M$ 의 격자판을 다 채운 경우가 되기 때문에 해당 경우 result가 1씩 늘어난다.

recur(int times) 함수에서는 다음과 같은 행동을 한다.

1. map[times / m][times % m] 에 1을 넣어도('넴모'를 배치해도) 2 * 2의 사각형이 만들어지지 않는다면, 해당 위치에 1을 넣은 다음, recur(times + 1) 을 실행한다.
   이는 계속 반복되기에, 해당 위치에 '넴모'를 두었다고 가정한 뒤, 다음 위치부터 마지막이 될 때까지 조건에 부합하고, 가능할 수 있는 모든 경우를 시도해본다고 할 수 있다.
2. map[times / m][times % m] 에 0을 넣어본 뒤, recur(times + 1) 을 실행한다.
   이 경우는 사각형 조건을 확인할 필요 없이 모든 위치에서 실행할 수 있다.
3. times 가 $N \times M$와 같다면, 조건을 맞춰 이 격자판의 모든 곳을 채웠기에 result += 1을 수행하고 마친다.

따라서 모든 곳의 위치가 조건에 부합하는 선에서 1일 때/ 0일 때를 모두 수행해볼 수 있게 된다.

답안 코드 링크 (Github)

Github Solution Link

정답 코드

#include <iostream>
#include <vector>
#define fastio                      \
	ios_base::sync_with_stdio(false); \
	cin.tie(NULL);                    \
	cout.tie(NULL)
using namespace std;

bool map[26][26];
int result, n, m;
void recur(int times);

int main(void)
{
	cin >> n >> m;
	recur(0);
	cout << result << "\n";
	return (0);
}

void recur(int times)
{
	int x = times / m, y = times % m;

	if (times == n * m)
	{
		result++;
		return;
	}
	if (!(x > 0 && y > 0 && (map[x - 1][y] && map[x][y - 1] && map[x - 1][y - 1])))
	{
		map[x][y] = true;
		recur(x * m + y + 1);
		map[x][y] = false;
	}
	map[x][y] = false;
	recur(x * m + y + 1);
	map[x][y] = false;	
}