BaekJoon 1941번: 소문난 칠공주(C++)

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

1941번: 소문난 칠공주

풀이법

1) 백트래킹과 BFS를 섞어야지만 풀 수 있는 문제이다.

2) 기존의 2차원 배열에서 DFS 형식으로는 십자가 형태의 값들을 체크할 수 없기에 1차원 배열로 만든 백 트래킹과 인접한 행렬임을 확인하기 위한 BFS를 활용하였다.

3) 7명을 백트래킹으로 선정한 이후, 

0  1   2  3  4

5  6   7  8  9

10 11 12 13 14

15 16 17 18 19

20 21 22 23 24

다음과 같은 인덱스로 되어 있는 것을 [i/5][i%5]로 만들게 되면 2차원 배열로 만들 수 있다.

BFS를 순회하며 7명이 인접해 있는지를 확인했으며 모두 인접하였으면 ans를 1 증가시켜 경우의 수를 모두 구하여 주었다.

 

#include <string>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int vx[4] = { 1,0,0,-1 };
int vy[4] = { 0,1,-1,0 };
char arr[26];
bool visited[26];
bool visitedC[5][5];
int ans = 0;
void bfs()
{
	for (int i = 0; i < 5; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			visitedC[i][j] = false;
		}
	}
	int cnt = 0;
	queue<pair<int,int>> q;
	for (int i = 0; i < 25; i++)
	{
		if (visited[i])
		{
			q.push({ i / 5,i % 5 });
			visitedC[i / 5][i % 5] = true;
			cnt++;
			break;
		}
	}
	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second;
		q.pop();
		if (cnt == 7)
		{
			ans++;
			break;
		}
		for (int i = 0; i < 4; i++)
		{
			int nextX = nowX + vx[i];
			int nextY = nowY + vy[i];
			if (nextX < 0 || nextY < 0 || nextX >= 5 || nextY >= 5)
				continue;
			if (visited[nextX * 5 + nextY] && !visitedC[nextX][nextY])
			{
				visitedC[nextX][nextY] = true;
				q.push({ nextX,{nextY} });
				cnt++;
			}
		}
	}

}
void backtracking(int index, int s, int cnt)
{
	if (cnt == 7)
	{
		if (s >= 4)
		{
			//인접했는지 확인 들어간 값들이
			bfs();
		}
	}
	for (int i = index + 1; i <= 24; i++)
	{
		if (!visited[i])
		{
			visited[i] = true;
			if (arr[i] == 'S')
				backtracking(i, s + 1, cnt + 1);
			else
				backtracking(i, s, cnt + 1);
			visited[i] = false;
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	for (int i = 0; i <25; i++)
	{
		char c; cin >> c;
		arr[i] = c;
	}

	//백트래킹으로 7개 씩 묶기
	backtracking(-1, 0, 0);
	cout << ans;
}