[BOJ] 1941_소문난 칠공주 with cpp

# 생각

백트래킹과 BFS를 둘 다 사용해서 해결 가능하다

 

기존 BFS의 방문 배열과 추가로 칠공주로 선택된 학생들의 배열로

조건에 맞게 BFS를 돌려 인접학생을 체크해줘야한다

 

또한 우위를 점하고 있는지 체크를 해야하므로

선택된 조합의 배열에서 'S'인 개수를 세어 4이상일 때만 반환하도록 해준다

 

 

# 전체 코드

// 2s, 256MB
// 5*5 combination 7 --> 25C7 = 480700가지 경우의 수
#include <bits/stdc++.h>
using namespace std;

bool bUsed[25];	// 조합시 선택된 수 체크

int coord[5][5];
bool bVis[5][5];	// 기존 BFS 방문 체크
bool bSelect7[5][5];	// 칠공주로 선택된 학생들
int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
int ans;
queue<pair< int, int >> q;

void Input()
{
	for (int i = 0; i < 5; i++)
	{
		string input;
		cin >> input;
		for (int j = 0; j < 5; j++)
		{
			if (input[j] == 'Y') coord[i][j] = 1;
			else if (input[j] == 'S') coord[i][j] = 2;
		}
	}
}
// 인접해 있는지 체크
bool IsAdj()
{
	// Array Init
	for (int i = 0; i < 5; i++)
	{
		fill(bVis[i], bVis[i] + 5, 0);
		fill(bSelect7[i], bSelect7[i] + 5, 0);
	}

	for (int i = 0; i < 25; i++)
	{
		if (bUsed[i] == true)
		{
			// (0,0) 부터 (4,4)까지 25개의 좌표 대입
			int x = i / 5;
			int y = i % 5;
			bSelect7[x][y] = true;
			if (q.empty())	// BFS 시작점 설정
			{
				q.push({ x,y });
				bVis[x][y] = true;
			}
		}
	}

	int cnt = 1;
	while (!q.empty())
	{
		int x, y;
		tie(x, y) = q.front();
		q.pop();
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = x + dx[dir], ny = y + dy[dir];
			if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5 || bVis[nx][ny] == true || bSelect7[nx][ny] == false)
			{
				// 범위에서 벗어났거나(OOB), 이미 방문한 배열이거나, 7공주가 아닐경우
				continue;
			}
			cnt++;
			q.push({ nx,ny });
			bVis[nx][ny] = true;
		}
	}
	if (cnt == 7) return true;
	return false;
}
// 우위를 점하고 있는지 체크
bool HaveEdge()
{
	int cnt = 0;
	for (int i = 0; i < 25; i++)
	{
		if (bUsed[i] == true)
		{
			// 5*5 x좌표, y좌표
			int x = i / 5;
			int y = i % 5;
			if (coord[x][y] == 2) cnt++;
		}
	}
	if (cnt >= 4) return true;
	else return false;
}
// backtracking DFS
void FuncRecursive(int depth, int start)
{
	if (depth == 7)
	{
		if (HaveEdge() == true)
		{
			if (IsAdj() == true) ans++;
		}
		return;
	}
	for (int i = start; i < 25; i++)
	{
		if (bUsed[i] == false)
		{
			bUsed[i] = true;
			FuncRecursive(depth + 1, i);
			bUsed[i] = false;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	Input();
	FuncRecursive(0, 0);
	cout << ans;
}

 

 

# next_permutation을 이용한 코드

#include <bits/stdc++.h>
using namespace std;

string graph[5];
int dx[4] = { 1,-1,0,0 }, dy[4] = { 0,0,1,-1 };
int ans;

void dfs2()
{
	vector<int> v;
	for (int i = 0; i < 25; i++)
	{
		v.push_back(i < 7 ? 0 : 1);	// 25명 중 7명 후보 선택
	}
	do
	{
		queue<pair<int, int>> q;
		int cnt = 0, adj = 0;	// 후보들 중 이다솜파의 수, 인접한 사람의 수
		bool bP7[5][5] = {}, bVis[5][5] = {};
		for (int i = 0; i < 25; i++)
		{
			if (v[i] == 0)	// 후보로 선택되었다면
			{
				int x = i / 5;
				int y = i % 5;
				bP7[x][y] = true;	// 칠공주 좌표 대입
				if (q.empty())	// BFS 시작점 설정
				{
					q.push({ x,y });
					bVis[x][y] = true;
				}
			}
		}
		while (!q.empty())
		{
			int x, y;
			tie(x, y) = q.front();
			q.pop();
			adj++;
			cnt += graph[x][y] == 'S';
			for (int dir = 0; dir < 4; dir++)
			{
				int nx = x + dx[dir], ny = y + dy[dir];
				if (nx < 0 || nx >= 5 || ny < 0 || ny >= 5 || !bP7[nx][ny] || bVis[nx][ny])
				{
					continue;	// OOB, 7공주가 아닐 경우, 이미 방문한 경우
				}
				q.push({ nx,ny });
				bVis[nx][ny] = true;
			}
		}
		ans += (adj >= 7 and cnt >= 4);	// 인접해 있는지, 우위를 점하고 있는지
	} while (next_permutation(v.begin(), v.end()));
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	for (int i = 0; i < 5; i++)
	{
		cin >> graph[i];
	}
	dfs2();
	cout << ans;
}

 

---

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

1941번: 소문난 칠공주