[BOJ 1799, 약간 어려움] 비숍 (C++)

개인적인 난이도

약간 어려움

 

 

---

실패한 풀이)

체스판에서 대각선을 체크하면서 말을 놓는 백트래킹의 구현은 그렇게 어렵지 않으나, 그냥 백트래킹하면 시간초과가 나게 되는 문제이다. 약간의 아이디어로 시간복잡도를 크게 줄일 수 있다.

 

안되는 이유

최악의 경우, 10*10 의 배열의 모든 칸에 비숍을 배치할 수 있다

검사할 칸의 개수 100개 -> 백트래킹 없이 완전탐색할 경우 2^100~=1e30 대략 1e22초 소요

백트래킹으로 탐색하며 비숍을 배치할 수 있는 위치에만 비숍을 배치한다고 해도 시간초과가 난다.

그 이유는 이러하다. 10*10 크기의 2차원 배열의 경우 20+20 개의 대각선을 그릴 수 있다.

인정?? 인정~

 

비숍을 어느 한 위치에 놓을때마다 우상향 방향 대각선 1개와 좌상향 방향 대각선 1개에 비숍을 놓을 수 없게 된다.

그렇다고 하면 총 경우의 수는,

 

**비숍을 판에 배치하는 경우의 수가 18개부터 시작하는 이유는, https://www.acmicpc.net/problem/1560 이 문제를 풀어보면 알 수 있다.

 

18개의 비숍을 판에 배치할 경우 : (20*20) * (19*19) * (18*18) ... (3*3)

17개의 비숍을 판에 배치할 경우 : (20*20) * (19*19) * (18*18) ... (4*4)

...

이런식으로 계산될 것이라고 예측할 수 있다. (필자가 수학적 증명에는 약하니 이해해주길 바란다.)

이렇게만 해도 계산해야하는 경우의 수가 (20!)^2를 넘어갈 것이라고 예상할 수 있고,

20! = 2.432902e+18 이므로 벌써부터 시간 제한을 한참 넘어간다.

 

실패 코드 (TLE)

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
using namespace std;

int N,ans;
int P[10][10],B[10][10];

bool check(int a,int b){
	int na,nb;
	na=a;nb=b;
	while (--na>=0&&--nb>=0)if(B[na][nb]==1)return 0;
	na=a;nb=b;
	while (--na>=0&&++nb<N)if(B[na][nb]==1)return 0;
	na=a;nb=b;
	while (++na<N&&--nb>=0)if(B[na][nb]==1)return 0;
	na=a;nb=b;
	while (++na<N&&++nb<N)if(B[na][nb]==1)return 0;
	return 1;
}

void cntans(){
	int cnt = 0;
	for (int i = 0; i < N; i++)
	for (int j = 0; j < N; j++)
	if(B[i][j])cnt++;
	ans=max(ans,cnt);
}
void bt(int k){
	int na,nb;
	while (k<N*N)
	{
		na = k/N; nb = k%N;
		++k;
		if(P[na][nb]&&check(na,nb)){
			B[na][nb]=1;
			bt(k);
			B[na][nb]=0;
		}
	}
	cntans();
}

int main(void) {
	fastio;
	cin>>N;	
	for (int i = 0; i < N; i++)
	for (int j = 0; j < N; j++)
	cin>>P[i][j];
	bt(0);
	cout<<ans;
	return 0;
}

 

 

---

성공한 풀이)

아이디어가 필요하다.

비숍은 같은 대각선으로만 영향을 미친다. 검은색 칸에 있는 비숍은 흰색 칸에 있는 비숍의 대각선과 절대 겹치지 않는다.

그러므로 검은색 칸과 흰색칸을 따로 백트래킹한 뒤 그 경우의 수를 더하면 시간복잡도가 크게 줄어든다.

위에서, 시간복잡도 계산이

18개의 비숍을 배치할 경우 : (20*20) * (19*19) * (18*18) ... (3*3)

17개의 비숍을 배치할 경우 : (20*20) * (19*19) * (18*18) ... (4*4)

이런식으로 전개되면서 시간복잡도가 (2N!)^2?? 이런식으로 될 것이라고 예상할 수 있었다. N이 커질수록 시간복잡도가 매우 빠르게 증가한다.

검은색이나 흰색 칸에만 비숍을 배치할 경우, N을 절반으로 줄일 수 있다.

20! = 2.432902e+18 와, 10! = 3628800의 차이는 대충 봐도 매우 크다

성공한 코드

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define ll long long
using namespace std;

int N,ansb,answ;
int P[10][10],B[10][10],W[10][10];

bool checkB(int a,int b){
	int na,nb;
	na=a;nb=b;
	while (--na>=0&&--nb>=0)if(B[na][nb]==1)return 0;
	na=a;nb=b;
	while (--na>=0&&++nb<N)if(B[na][nb]==1)return 0;
	na=a;nb=b;
	while (++na<N&&--nb>=0)if(B[na][nb]==1)return 0;
	na=a;nb=b;
	while (++na<N&&++nb<N)if(B[na][nb]==1)return 0;
	return 1;
}
bool checkW(int a,int b){
	int na,nb;
	na=a;nb=b;
	while (--na>=0&&--nb>=0)if(W[na][nb]==1)return 0;
	na=a;nb=b;
	while (--na>=0&&++nb<N)if(W[na][nb]==1)return 0;
	na=a;nb=b;
	while (++na<N&&--nb>=0)if(W[na][nb]==1)return 0;
	na=a;nb=b;
	while (++na<N&&++nb<N)if(W[na][nb]==1)return 0;
	return 1;
}
void cntbans(){
	int cnt = 0;
	for (int i = 0; i < N; i++)
	for (int j = 0; j < N; j++)
	if(B[i][j])cnt++;
	ansb=max(ansb,cnt);
}
void cntwans(){
	int cnt = 0;
	for (int i = 0; i < N; i++)
	for (int j = 0; j < N; j++)
	if(W[i][j])cnt++;
	answ=max(answ,cnt);
}
void btwhite(int k){//1부터 시작
	int na,nb;
	while (k<N*N)
	{
		na = k/N; nb = k%N;
		if(N%2==1)k+=2;
		else{
			if((k+1)%N==0)k++;
			else if((k+2)%N==0)k+=3;
			else k+=2;
		}
		if(P[na][nb]&&checkW(na,nb)){
			W[na][nb]=1;
			btwhite(k);
			W[na][nb]=0;
		}
	}
	cntwans();
}
void btblack(int k){//0부터 시작
	int na,nb;
	while (k<N*N)
	{
		na = k/N; nb = k%N;
		if(N%2==1)k+=2;
		else{
			if((k+1)%N==0)k++;
			else if((k+2)%N==0)k+=3;
			else k+=2;
		}
		if(P[na][nb]&&checkB(na,nb)){
			B[na][nb]=1;
			btblack(k);
			B[na][nb]=0;
		}
	}
	cntbans();
}
int main(void) {
	fastio;
	cin>>N;	
	for (int i = 0; i < N; i++)
	for (int j = 0; j < N; j++)
	cin>>P[i][j];
	btblack(0);
	btwhite(1);
	cout<<ansb+answ;
	return 0;
}

 

---

더 좋은 풀이)

더 좋은 아이디어가 적용된 풀이를 찾았다 제출번호 51192406

https://www.acmicpc.net/source/51192406

로그인

 

적용된 아이디어

 

이사람은 사용된 대각선인지 사용되지 않은 대각선인지 구분하기 위해 매우 세련된 방법을 썼다

무려 2차원 배열의 대각선에 인덱싱이 가능하다.

가로 N칸 세로 N칸짜리 2차원 배열의 경우, 그 우상향 방향 대각선은 2N 가지가 있음.

우상향 방향 대각선은 x+y의 값으로 인덱싱이 가능하다

좌상향 방향 대각선도 똑같이 2N가지가 발생하고, x-y+N-1으로 인덱싱이 가능하다

대각선 인덱싱을 통해 N*N배열의 모든 대각선 점들을 직접 방문하면서 체크할 필요가 없어지고, 내 코드의 18% 속도로 동작한다.

 

여담)

1. vector.assign 함수를 사용할 경우 벡터를 선언하면서 어떤 값 또는 컨테이너로 쉽게 초기화가 가능
2. 골드 이상 문제부터는 문제를 접근하면서의 아이디어가 특히 중요해지는 것 같다.