백준 22359 흔한 타일 색칠 문제

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

22359번: 흔한 타일 색칠 문제

 

풀이 

타일은 다음과 같은 모양으로 배치할 수 있습니다.

 

좀 더 큰 모형은 다음과 같은 모양으로 배치되고

 

조금 더 큰 모형은 아래와 같이 배치됩니다!!

 

 

ㄱ자 모양은 위의 방식대로 타일 배치한다면 만들 수 있다는 것을 알게 되었습니다.

재귀 함수를 통해서 해당 모양을 만들면 됩니다.

 

 

 

문제의 목표는 타일이 하나 때어져 있는 한 변이 2^K인 정사각형을 모두 채우는 방법을 출력하는 것입니다.

 

 

 

 

 

이해를 돕기위한 한 가지 시뮬레이션을 돌려보겠습니다.

 

 우리가 채워야할 정사각형입니다. 빨간 곳은 빠져있는 타일입니다.

 

 

타일을 4등분했을때 타일이 빠져 있는 부분을 제외하고 

ㄱ자 모양으로 타일을 채웁니다.

 

 

채우고 남은 부분은 정사각형 모양으로 남을 것입니다.

남은 정사각형에서도 4등분을 실행하고 빠져있는 부분을 제외한 부분을 ㄱ자로 채웁니다.

 

위의 과정을 반복하면 빠진 부분을 제외한 모든 부분을 ㄱ자로 채울 수 있습니다.

 

 

해당 문제가 단순히 타일만 채우면 되는 단순한 문제면 쉽겠지만

문제는 인접한 타일의 색이 달라야 한다는 것입니다!!

 

 

일단 타일을 다음과 위와 같이 배치를 하면

인접한 타일의 색이 모두 다르게 배치됩니다.

 

큰 ㄱ자도 다음과 같이 안겹치게 배치된다.

 

ㄱ자는 다음과 같이 모두 배치하면되지만 빈 타일에 해당하는

제일 작은 ㄱ은 어떤 색으로 배치해야하는지 알아내야 됩니다.

 

위의 타일을 자세히 보면 파랑과 초록이 번갈아서 나오는 것을 알 수 있습니다.

위의 타일을 빨간색 타일을 없이 보면 아래와 같이 보일 겁니다.

 

 

파랑 초록이 반복되는 순서를 통해서 우리가 채워야할 색을 알아낼 수 있습니다. 

 

 

 

구현이 조금 어려운 문제입니다. 풀이만 보고 스스로 구현 할 수 있도록 연습합시다!!

 

코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define int long long
#define float double

int T, N;
char MAP[2000][2000];

void Color(int a, int b, int w, char c, int dic)
{
	for (int j = b; j < b + w; j++)
		for (int i = a; i < a + w; i++)
		{
			if (dic == 0 && a + w * 0.5f <= i && b + w * 0.5f <= j)
				continue;
			if (dic == 1 && a + w * 0.5f > i && b + w * 0.5f <= j)
				continue;
			if (dic == 2 && a + w * 0.5f > i && b + w * 0.5f > j)
				continue;
			if (dic == 3 && a + w * 0.5f <= i && b + w * 0.5f > j)
				continue;
			MAP[j][i] = c;
		}
}

void DFS(int a, int b, int w, int dic)
{
	if (w == 4)
	{
		if (dic == 0)
		{
			Color(a, b, w * 0.5, 'b', 0);
			Color(a + w * 0.25, b + w * 0.25, w * 0.5, 'a', 0);
			Color(a, b + w * 0.5, w * 0.5, 'c', 3);
			Color(a + w * 0.5, b, w * 0.5, 'c', 1);
		}
		else if (dic == 1)
		{
			Color(a, b, w * 0.5, 'b', 0);
			Color(a + w * 0.5, b, w * 0.5, 'c', 1);
			Color(a + w * 0.25, b + w * 0.25, w * 0.5, 'a', 1);
			Color(a + w * 0.5, b + w * 0.5, w * 0.5, 'b', 2);
		}
		else if (dic == 2)
		{
			Color(a + w * 0.25, b + w * 0.25, w * 0.5, 'a', 2);
			Color(a + w * 0.5, b + w * 0.5, w * 0.5, 'b', 2);
			Color(a + w * 0.5, b , w * 0.5, 'c', 1);
			Color(a, b + w * 0.5, w * 0.5, 'c', 3);
		}
		else if (dic == 3)
		{
			Color(a, b, w * 0.5, 'b', 0);
			Color(a + w * 0.5, b + w * 0.5, w * 0.5, 'b', 2);
			Color(a + w * 0.25, b + w * 0.25, w * 0.5, 'a', 3);
			Color(a, b + w * 0.5, w * 0.5, 'c', 3);
		}
		return;
	}

	if (dic == 0)
	{
		DFS(a, b, w * 0.5, 0);
		DFS(a + w * 0.5, b, w * 0.5, 1);
		DFS(a, b + w * 0.5, w * 0.5, 3);
		DFS(a + w * 0.25, b + w * 0.25, w * 0.5, 0);
	}
	else if (dic == 1)
	{
		DFS(a, b, w * 0.5, 0);
		DFS(a + w * 0.5, b, w * 0.5, 1);
		DFS(a + w * 0.25, b + w * 0.25, w * 0.5, 1);
		DFS(a + w * 0.5, b + w * 0.5, w * 0.5, 2);
	}
	else if (dic == 2)
	{
		DFS(a + w * 0.5, b, w * 0.5, 1);
		DFS(a, b + w * 0.5, w * 0.5, 3);
		DFS(a + w * 0.5, b + w * 0.5, w * 0.5, 2);
		DFS(a + w * 0.25, b + w * 0.25, w * 0.5, 2);
	}
	else if (dic == 3)
	{
		DFS(a, b, w * 0.5, 0);
		DFS(a, b + w * 0.5, w * 0.5, 3);
		DFS(a + w * 0.25, b + w * 0.25, w * 0.5, 3);
		DFS(a + w * 0.5, b + w * 0.5, w * 0.5, 2);
	}
}

int x, y;
void DFS2(int a, int b,int w)
{
	if (w == 2)
	{
		int temp = a / 2 + b / 2;
		char nc = temp % 2 == 0 ? 'b' : 'c';
		if (x < a + w * 0.5 && y < b + w * 0.5)
		{
			Color(a, b, w, nc, 2);
		}
		else if (x < a + w * 0.5 && y >= b + w * 0.5)
		{
			Color(a, b, w, nc, 1);
		}
		else if (x >= a + w * 0.5 && y < b + w * 0.5)
		{
			Color(a, b, w, nc, 3);
		}
		else if (x >= a + w * 0.5 && y >= b + w * 0.5)
		{
			Color(a, b, w, nc, 0);
		}

		return;
	}
	if (x < a + w * 0.5 && y < b + w * 0.5)
	{
		DFS(a, b, w, 2);
		DFS2(a, b, w * 0.5);
	}
	else if (x < a + w * 0.5 && y >= b + w * 0.5)
	{
		DFS(a, b, w, 1);
		DFS2(a, b + w * 0.5, w * 0.5);
	}
	else if (x >= a + w * 0.5 && y < b + w * 0.5)
	{
		DFS(a, b, w, 3);
		DFS2(a + w * 0.5, b , w * 0.5);
	}
	else if (x >= a + w * 0.5 && y >= b + w * 0.5)
	{
		DFS(a, b, w, 0);
		DFS2(a + w * 0.5, b + w * 0.5, w * 0.5);
	}
}

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	std::cout.tie(NULL);
	
	cin >> T >> N;
	while (T--)
	{
		for (int i = 0; i < 2000; i++)
			for (int j = 0; j < 2000; j++)
				MAP[i][j] = ' ';

		cin >> y >> x;
		x--;
		y--;
		MAP[y][x] = '@';
		DFS2(0, 0, 1 << N);

		for (int i = 0; i < (1 << N); i++)
		{
			for (int j = 0; j < (1 << N); j++)
				cout << MAP[i][j];
			cout << endl;
		}
	}

}