백준 1799번 비숍

문제 링크입니다: https://www.acmicpc.net/problem/1799

1799번: 비숍

먼저 이 문제는 Crocus님의 코드를 참고하여 풀었습니다.

(https://www.crocus.co.kr/775)

 

체스 문제가 나오면 이분그래프를 통해 접근해야한다는 것을 Crocus님 통해 알 수 있었습니다.

비숍은 대각선으로 움직이기 때문에 좌상단부터 우하단, 좌하단부터 우상단까지 대각선을 통해 연결할 수 있는 타일에 각각 번호를 부여한 뒤 비숍이 위치할 수 있는 칸에 대해 이분 그래프를 형성하면 되는 문제였습니다.

더 자세한 내용은 Crocus님 블로그를 참고하시길 바랍니다.

 

	#include <iostream>
	#include <cstdio>
	#include <vector>
	#include <algorithm>
	using namespace std;
	const int MAX_N = 52;
	const int MAX_V = 102;
	vector<int> adj[MAX_V];
	vector<int> aMatch;
	vector<int> bMatch;
	int map[MAX_N][MAX_N];
	int visited[MAX_V];
	int visitedCnt;
	int Left[MAX_N][MAX_N];
	int Right[MAX_N][MAX_N];
	int N;
	int leftMax, rightMax;
	void fillLeft()
	{
	int y = 1;
	int x = N;
	int cnt = 1;
	// 오른쪽 위 시작 기준 대각선은 총 N번 반복
	for (int k = 0; k < 2 * N - 1; k++)
	{
	int tempY = y;
	int tempX = x;
	while (tempY <= N)
	{
	Left[tempY++][tempX++] = cnt;
	}
	cnt++;
	x--;
	}
	}
	void fillRight()
	{
	int y = N;
	int x = N;
	int cnt = 1;
	// 오른쪽 아래 시작 기준 대각선은 총 N번 반복
	for (int k = 0; k < 2 * N - 1; k++)
	{
	int tempY = y;
	int tempX = x;
	while (tempY > 0)
	{
	Right[tempY--][tempX++] = cnt;
	}
	cnt++;
	x--;
	}
	}
	bool DFS(int a)
	{
	if (visited[a] == visitedCnt)
	{
	return false;
	}
	visited[a] = visitedCnt;
	for (int next = 0; next < adj[a].size(); next++)
	{
	int b = adj[a][next];
	if (bMatch[b] == -1 || DFS(bMatch[b]))
	{
	aMatch[a] = b;
	bMatch[b] = a;
	return true;
	}
	}
	return false;
	}
	int bipartiteMatch()
	{
	aMatch = vector<int>(leftMax + 1, -1);
	bMatch = vector<int>(rightMax + 1, -1);
	int result = 0;
	for (int i = 1; i <= leftMax; i++)
	{
	visitedCnt++;
	result += DFS(i);
	}
	return result;
	}
	int main()
	{
	ios_base::sync_with_stdio(0);
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
	for (int j = 1; j <= N; j++)
	{
	cin >> map[i][j];
	}
	}
	fillLeft();
	fillRight();
	// 1일때만 간선 연결(0일때는 벽이니)
	int maxL = 0, maxR = 0;
	for (int i = 1; i <= N; i++)
	{
	for (int j = 1; j <= N; j++)
	{
	if (map[i][j] == 1)
	{
	adj[Left[i][j]].push_back(Right[i][j]);
	maxL = max(maxL, Left[i][j]);
	maxR = max(maxR, Right[i][j]);
	}
	}
	}
	// 이분매칭에 이용 될 n과 m은 maxL, maxR로 교체된다.
	leftMax = maxL;
	rightMax = maxR;
	cout << bipartiteMatch() << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~