[알고리즘] C++ 백준 1941 소문난 칠공주

 

백준 1941

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

1941번: 소문난 칠공주

 

풀이 전 나의 생각

우선 처음부터 BFS로 풀겠다고 접근하면 안된다.

왜냐하면 BFS는 자유로운 방향으로 'ㅜ' 나 'ㅏ' 의 방향처럼 퍼질 수는 있지만 역으로 다시 돌아와서 재탐색 하지 않는다.

그래서 모든 분기를 돌며 탐색을 진행하는 DFS와 같이 사용하면 쉽게 풀 수 있다.

 

DFS는 학생들의 모든 조합을 찾기 위해 사용한다.

이유는 모든 조합을 구하면 모든 경우의 수를 구할 수 있기 때문이다. 만약 이해가 잘 되지 않는다면 백준의 대표적인 백트래킹 문제인 N과 M 시리즈를 모두 풀고오면 도움이 될 것이다. 이렇게 DFS를 사용하여 나올 수 있는 최대 7크기의 모든 조합을 구한다.

 

다음으로는 내가 만든 조합이 '이다솜파' 가 4명 이상있는지 체크해야 한다.

방문한 곳을 탐색하며 '이다솜파' 가 확인된다면 값을 하나씩 올려준다.

여기서 i / 5, i % 5를 하는 이유는 방문한 곳을 2차원 배열의 위치 값으로 변환해주기 위해서다.

5를 나누는 이유는 현재 학생 배열의 크기를 2차원 배열로 받는다고 가정했을 때 5 * 5 이기 때문이다.

 

0, 1, 2 번째의 위치 값을 구한다고 가정하면

i = 1 -> ( 0 / 5 = 0, 0 % 5 = 0 ) 

i = 2 -> ( 1 / 5 = 0, 1 % 5 = 1 )

i = 3 -> ( 2 / 5 = 0, 2 % 5 = 2 )

이러한 형식으로 진행되며 2차원 좌표 값을 얻을 수 있다.

 

다음으로는 '이다솜파'가 4명 이상인 것이 확인 되었을 경우 7크기의 조합이 서로 이어져 있는지 확인해야 한다.

현재 visit배열에 담겨있는 값을 BFS 공간에 있는 배열에 받아 주고 탐색을 진행하기 위해 일곱 학생이 있는 공간의 시작점을 큐에 넣어준다.

 

복제한 배열을 탐색하면서 만약 학생이 있는 공간이면서 방문한 곳이 아닐 경우에 다음 위치로 이동하며 카운트를 증가시켜 준다. 만약에 안정적으로 이어져 있다면 카운트가 7이 되어 true를 반환해줄 것이고 끊겨져 있다면 최종 카운트가 7이 되지 못하고 false를 반환할 것이다. 

 

요약하자면

1. DFS를 이용하여 모든 조합 탐색

2. 조합의 크기가 7이 되면 '이다솜파' 가 4명 이상 있는지 확인, 아닐 시 1번으로

3. 4명 이상 있다면 학생이 모두 이어져 있는지 확인, 아닐 시 1번으로

4. 1,2,3을 모두 만족할 시 최종 결과 값 증가

5. 반복

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>

using namespace std;

int dx[] = { 0, 0, -1, 1 };
int dy[] = { 1, -1, 0, 0 };

string arr[25];
bool visit[25];
char seven[7];
int res = 0;

bool BFS() 
{
	queue <pair<int, int>> q;
	bool b_Visit[5][5];
	bool q_Visit[5][5];
	bool isInput = false;
	int cnt = 1;

	for (int i = 0; i < 5; ++i) 
	{
		fill(begin(b_Visit[i]), end(b_Visit[i]), false);
		fill(begin(q_Visit[i]), end(q_Visit[i]), false);
	}

	for (int i = 0; i < 25; i++)
	{
		if (visit[i])
		{
			int x = i / 5;
			int y = i % 5;

			b_Visit[x][y] = 1;

			if (!isInput)
			{
				q.push({ x, y });
				q_Visit[x][y] = 1;
				isInput = 1;
			}
		}
	}

	while (!q.empty())
	{
		if (cnt == 7) return true;

		pair<int, int> p = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = p.first + dx[i];
			int ny = p.second + dy[i];

			if (nx < 0 || ny < 0 || nx >= 5 || ny >= 5) continue;
			if (b_Visit[nx][ny] && !q_Visit[nx][ny])
			{
				cnt++;
				q_Visit[nx][ny] = 1;
				q.push({nx, ny});
			}
		}
	}

	return false;
}
void DFS(int idx, int cnt)
{
	if (cnt == 7)
	{
		int sCnt = 0;
		
		for (int i = 0; i < 25; i++)
		{
			if (visit[i])
			{
				int x = i / 5;
				int y = i % 5;

				if (arr[x][y] == 'S') sCnt++;
			}
		}

		if (sCnt >= 4 && BFS())
		{
			res++;
		}
		return;
	}
	
	for (int i = idx; i < 25; i++)
	{
		if (!visit[i])
		{
			visit[i] = 1;
			DFS(i, cnt + 1);
			visit[i] = 0;
		}
	}
}

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

	for (int i = 0; i < 5; i++)
	{
		cin >> arr[i];
	}
	
	DFS(0, 0);

	cout << res;
}