BOJ 1799. 비숍

🙇‍♀️[Gold I] 비숍 - 1799

문제 링크

성능 요약

메모리: 2020 KB, 시간: 44 ms

분류

백트래킹

제출 일자

2024년 2월 24일 19:41:50

문제 설명

서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. < 그림 1 >과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다.

< 그림 1 >

그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. < 그림 2 >에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 < 그림 3 >과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부분에는 비숍이 놓일 수 없지만 지나갈 수는 있다.

< 그림 2 >

< 그림 3 >

정사각형 체스판의 한 변에 놓인 칸의 개수를 체스판의 크기라고 한다. 체스판의 크기와 체스판 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 주어질 때, 서로가 서로를 잡을 수 없는 위치에 놓을 수 있는 비숍의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 한 줄씩 주어진다. 비숍을 놓을 수 있는 곳에는 1, 비숍을 놓을 수 없는 곳에는 0이 빈칸을 사이에 두고 주어진다.

출력

첫째 줄에 주어진 체스판 위에 놓을 수 있는 비숍의 최대 개수를 출력한다.

🚀풀이

시간 초과 문제를 해결하지 못했다.

내가 해결하려한 방법은 비숍을 놓는 모든 경우를 탐색하고 해당 경우가 문제의 조건에 부합하는지 판별하고 최대 비숍 개수를 세려고 했다.

DFS를 두 개 만들어서 각각 시도해봤는데 둘 다 시간초과가 나서 해결하지 못했다.

내가 처음에 생각한 코드는 아래와 같다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// 100개의 칸이 최대 값
// 시간 복잡도를 생각해보자.
// 모든 경우의 수를 탐색할 것이다.
// 한 위치에 비숍을 놓거나 안놓거나이니까
// 칸당 2개의 경우의 수
// 최대 2^100의 경우의 수가 나온다 -> 이렇게 탐색하면 시간내에 못푼다

void setting();
bool isOkay(pair<int, int> p);
void DFS(int L);
void printBoard();
void solve();

int n, cache[100], res = 0, cnt = 0;
vector<vector<int>> board;
vector<pair<int, int>> goodPos;
int dy[] = { 1, 1, -1, -1 }; // 좌측 하단, 우측 하단, 우측 상단, 좌측 상단.
int dx[] = { -1, 1, 1, -1 };
void setting()
{
	cin >> n;
	board = vector<vector<int>>(n + 1, vector<int>(n + 1));

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			cin >> board[i][j];
			if (board[i][j] == 1) // 놓을 수 있는 비숍 자리들.
				goodPos.push_back({ i, j });
		}
	}
}

// p위치에 비숍을 놓았을 때 괜찮은지 확인하는 함수.
bool isOkay(pair<int, int> p)
{
	int y = p.first;
	int x = p.second;
	if (board[y][x] == 1)
		return true;

	for (int i = 0; i < 4; ++i)
	{
		while (true)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < 1 || nx < 1 || ny > n || nx > n)
				break;
			// 다른 비숍이 있을 경우 잘못된 위치.
			if (board[ny][nx] == 2)
			{
				return false;
			}

			y = ny;
			x = nx;
		}

		y = p.first;
		x = p.second;
	}

	return true;
}

void DFS(int L)
{
	if (L == goodPos.size())
	{
		bool flag = true;
		for (int i = 0; i < goodPos.size(); ++i)
		{
			if (isOkay({ goodPos[i].first, goodPos[i].second }) == false)
			{
				flag = false;
				break;
			}

		}

		if (flag == true)
		{
			cnt = 0;

			for (int i = 0; i < goodPos.size(); ++i)
			{
				if (board[goodPos[i].first][goodPos[i].second] == 2)
					cnt++;
			}

			res = max(res, cnt);
		}
	}
	else
	{
		board[goodPos[L].first][goodPos[L].second] = 1;
		cache[L] = 1;
		DFS(L + 1);
		board[goodPos[L].first][goodPos[L].second] = 2;
		cache[L] = 2;
		DFS(L + 1);
	}
}

void printBoard()
{
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			cout << board[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

void bishop(int L)
{
	//printBoard();

	if (L == goodPos.size())
	{
		cnt = 0;

		for (int i = 0; i < goodPos.size(); ++i)
		{
			if (board[goodPos[i].first][goodPos[i].second] == 2)
				cnt++;
		}

		res = max(res, cnt);

		return;
	}
	else
	{
		board[goodPos[L].first][goodPos[L].second] = 2; // 이 위치에 비숍 놓기
		if (isOkay(goodPos[L]))
			bishop(L + 1);

		board[goodPos[L].first][goodPos[L].second] = 1; // 원복
		bishop(L + 1);
	}
}

void solve()
{
	setting();

	//DFS(0);
	bishop(0);
	cout << res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참 잘 푼거같은데 아쉽.

다른 사람들의 코드를 보니까 비숍을 특징을 이용해서 시간 복잡도를 줄였다.

흰칸에 있는 비숍은 흰칸으로만 이동이 가능하고 마찬가지로 검은칸에 있는 비숍은 검은칸으로만 이동이 가능하다.

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

void setting();
void printBoard();
void solve();

int n, res = 0, cnt = 0;
int board[11][11];
vector<pair<int, int>> arr;
vector<pair<int, int>> bishopPos;
void setting()
{
	cin >> n;

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			cin >> board[i][j];
			if (board[i][j] == 1 && (i + j) % 2 == 0) // 놓을 수 있는 비숍 자리들.
				arr.push_back({ i, j });
		}
	}
}

void printBoard()
{
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			cout << board[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

void bishop(int cnt, int L)
{
	if (cnt > res)
		res = cnt;
	if (L == arr.size())
		return;

	bool flag = true;
	for (int i = 0; i < bishopPos.size(); ++i)
	{
		if (abs(arr[L].first - bishopPos[i].first) == abs(arr[L].second - bishopPos[i].second))
		{
			flag = false;
			break;
		}
	}
	if (flag == true)
	{
		bishopPos.push_back({ arr[L].first, arr[L].second });
		bishop(cnt + 1, L + 1);
		bishopPos.pop_back();
	}
	bishop(cnt, L + 1);

	return;
}

void solve()
{
	setting();

	int ans = 0;
	bishop(0, 0);
	ans += res;
	res = 0;
	arr.clear();

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if (board[i][j] == 1 && (i + j) % 2 == 1)
				arr.push_back({ i, j });
		}
	}
	bishop(0, 0);
	ans += res;
	res = 0;
	arr.clear();

	cout << ans;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}