1941번: 소문난 칠공주

문제 설명

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

1941번: 소문난 칠공주

[문제]

 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다.

 위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다.

1. 이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다.
2. 강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다.
3. 화합과 번영을 위해, 반드시 ‘이다솜파’의 학생들로만 구성될 필요는 없다.
4. 그러나 생존을 위해, ‘이다솜파’가 반드시 우위를 점해야 한다. 따라서 7명의 학생 중 ‘이다솜파’의 학생이 적어도 4명 이상은 반드시 포함되어 있어야 한다.

 여학생반의 자리 배치도가 주어졌을 때, ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 구하는 프로그램을 작성하시오.

 

[입력]

 'S'(이다‘솜’파의 학생을 나타냄) 또는 'Y'(임도‘연’파의 학생을 나타냄)을 값으로 갖는 5*5 행렬이 공백 없이 첫째 줄부터 다섯 줄에 걸쳐 주어진다.

 

[출력]

 첫째 줄에 ‘소문난 칠공주’를 결성할 수 있는 모든 경우의 수를 출력한다.

 

[예제 입력 1]

YYYYY
SYSYS
YYYYY
YSYYS
YYYYY

[예제 출력 1]

2

---

풀이

 초반 문제의 해결을 위해선 7개 칸으로 이루어진 특정 모양을 만들어 내야 하는데, DFS나 BFS를 적용한 탐색으로는 해당 모양을 만들어 낼 수가 없다. 결국 이어진 모양을 직접 만들어낼 수는 없고 조합을 통해 25개 좌석 중 7개를 뽑고, 해당 7개 좌석이 모두 연결되어 있는 지를 확인해야 한다. 그런 다음 해당 모양이 맞다면 좌석을 파악해 S가 4개 이상인 경우에만 답에 1을 더하는 것으로 해결했다.

 25개 중 7개의 좌석을 뽑는 것은 next_permutation() 함수를 적용해 해결했고, 이후 뽑은 7개의 좌석의 연결 상태를 파악하는 데는 BFS를 적용했다. 모든 좌석이 연결되어있다면 BFS를 통해 모두 방문할 수 있기 때문에, BFS를 통해 좌석들을 방문하고 해당 좌석들이 모두 방문되어 있는 지를 확인했다.

 앞선 설명에서는 모양을 만들고 좌석을 확인한다 했지만, 최종 코드에서는 이미 좌석을 뽑는 시점에서 해당 좌석의 'S' 여부를 확인하는게 훨씬 쉬워 먼저 개수를 파악하고 4개 이상인 경우에만 연결 상태 파악을 진행하는 것으로 했다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

char map[5][5]; //교실 배치 저장
int visited[25] = { 0, }; //탐색용 방문 배열
vector<int> permutation(25); //순열용 배열

void check(vector<int> pos, int& answer) {//7개 위치 확인
	memset(visited, 0, sizeof(visited));
	queue<int> q;
	q.push(pos[0]);

	while (!q.empty()) {//BFS를 통해 책상 연결성 파악
		int here = q.front(); q.pop();
		int r = here / 5, c = here % 5;

		if (visited[here] == 1)
			continue;

		visited[here] = 1;

		if (r > 0&& permutation[here - 5] == 1)
			q.push(here - 5);

		if (r < 4 && permutation[here + 5] == 1)
			q.push(here + 5);

		if (c > 0 && permutation[here - 1] == 1)
			q.push(here - 1);

		if (c < 4 && permutation[here + 1] == 1)
			q.push(here + 1);
	}

	for (int i = 0; i < 7; i++) {//연결 확인
		if (visited[pos[i]] == 0) //가지 못한 곳이 있으면(연결 x)
			return;
	}

	++answer; //경우의 수 + 1
}

int main() {
	string s;
	int sCount = 0, answer = 0;

	for (int i = 18; i < 25; i++)
		permutation[i] = 1;

	for (int i = 0; i < 5; i++) {//입력 처리
		cin >> s;
		for (int j = 0; j < 5; j++) {
			map[i][j] = s[j];
		}
	}

	do {//조합을 찾아 위치 확인
		vector<int> pos;
		sCount = 0;

		for (int i = 0; i < permutation.size(); i++) {
			if (permutation[i] == 1) {
				pos.push_back(i);

				if (map[i / 5][i % 5] == 'S')
					++sCount;
			}
		}

		if (sCount >= 4) //'S'가 4개 이상인 경우에만 확인
			check(pos, answer);
		
	} while (next_permutation(permutation.begin(), permutation.end()));

	cout << answer;
	
	return 0;
}

---

결과