[C언어 / 백준 - 1941번] 소문난 칠공주 (백트래킹 -> DFS/BFS)

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

1941번: 소문난 칠공주

문제

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

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

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

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

입력

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

출력

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

 

처음에는 하나 하나 DFS/BFS를 이용하여 7명을 결성하고 그 7명 중 이다솜파가 몇명인지 확인하는 식으로 짰다.

하지만 계속해서 실패했고, 그 문제점을 찾고자 다시 문제를 읽고 또 읽었다. 그리고 질문검색을 통해 다른 사람들이 생각한 방식을 보기도 했다.  처음 내가 생각한 풀이로는 이 문제를 해결하기에 적합하지 않았고, 이 문제는 조합과 DFS/BFS를 모두 사용해야하는 문제이다.

 

천천히 다시 살펴보면 충분히 어떤 과정으로 해결할 수 있는지 알아챌 수 있지만. 계속해서 한 가지 방법에만 생각하고 그 풀이로만 하려다보니 다른 방식의 풀이를 떠올릴 수 없었다.

 

이 문제를 간단히 보자면,

25명 중 7명을 뽑고, 그 7명 중 이다솜파가 4명 이상이면서 모두 인접해있는지 그 개수를 찾기만 하면 되는 문제였던 것이다.

25명 중 7명을 뽑는 것은 조합으로 해결하고,

인접해 있는 것은 BFS로 해결하면 되는 것이다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#define dep(i,a,b) for(int i=a;i<b;i++)
#define fep(i,a,b) for(int i=a;i<=b;i++)
#define swap(type,x,y) do{type t=x; x=y; y=t;} while(0)
#define MAX(a,b) a<b?b:a
#define MIN(a,b) a<b?a:b
struct node {
	int x;
	int y;
};

int head = 0, tail = 0;
int top = 0;
struct node Queue[500];
struct node Stack[500];

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

char map[5][5];
int visited[25];
int ans = 0;

void Stack_Push(int x_, int y_) {
	struct node temp;
	temp.x = x_;
	temp.y = y_;
	Stack[top++] = temp;
}

struct node Stack_Pop(void) {
	struct node temp = Stack[--top];
	return temp;
}

struct node Stack_Top(void) {
	struct node temp = Stack[top - 1];
	return temp;
}

int Stack_Is_Empty(void) {
	if (top <= 0)
		return 0;
	else
		return 1;
}

void Queue_Enque(int x_, int y_) {
	struct node temp;
	temp.x = x_;
	temp.y = y_;
	Queue[tail] = temp;
	tail = (tail + 1) % 50;
}

struct node Queue_Deque(void) {
	struct node temp;
	temp = Queue[head];
	head = (head + 1) % 50;
	return temp;
}

int Queue_Is_Empty(void) {
	if (head == tail)
		return 0;
	else
		return 1;
}

void Input() {
	for (int i = 0; i < 5; i++)
		scanf("%s", map[i]);
}

bool check_near_seat() {
	struct node first = Stack_Top();
	bool flag[7] = { false, };
	Queue_Enque(first.x, first.y);
	int cnt = 1;

	while (Queue_Is_Empty()) {
		struct node k = Queue_Deque();
		int nextX, nextY;
		for (int ps = 0; ps < 6; ps++) {
			if (flag[ps]) continue;
			for (int i = 0; i < 4; i++) {
				nextX = k.x + dx[i];
				nextY = k.y + dy[i];
				if (nextX == Stack[ps].x && nextY == Stack[ps].y) {
					Queue_Enque(nextX, nextY);
					flag[ps] = true;
					cnt++;
				}
			}
		}
	}
	if (cnt == 7)
		return true;
	else
		return false;
}

void dfs(int index, int cnt_s, int cnt_y) {
	if (cnt_y + cnt_s == 7) {
		if (cnt_y > cnt_s) 
			return;
		if (check_near_seat()) 
			ans++;
		return;
	}
	for (int i = index; i < 25; i++) {
		if (visited[i]) continue;
		int R = i / 5;
		int C = i % 5;
		Stack_Push(C, R);
		visited[i] = 1;
		if (map[R][C] == 'Y')
			dfs(i + 1, cnt_s, cnt_y+1);
		else
			dfs(i + 1, cnt_s+1, cnt_y);
		visited[i] = 0;
		Stack_Pop();
	}
}

int main() {
	Input();
	dfs(0, 0, 0);
	printf("%d\n", ans);

	return 0;
}