[백준] 1941-소문난 칠공주(C++)

문제링크:www.acmicpc.net/problem/1941

1941번: 소문난 칠공주

 

백트래킹 문제입니다. 전체가 검색해주는 것이 아니라 임도연파 학생이 4이상이 될때 가지치기를 해주어야 합니다. (근데 제거 해주지 않아도 ac통과합니다.)

 

F 모양처럼 일반적인 방식의 dfs, bfs로는 구현할 수 없다는 것을 알게되었습니다.

모든 좌표를 탐색해야하는데 어떻게 구현할지 고민했습니다.

그리고 아래처럼 구현했습니다.

for (int i = y; i < 5; i++) {
		for (int j = (i == y ? x : 0); j < 5; j++) {
			if (chk[i][j] == 0) {
				chk[i][j] = 1;
				dfs(cnt + 1, i, j, arr[i][j] == 'S' ? som + 1 : som, arr[i][j] == 'Y' ? yim + 1 : yim);
				chk[i][j] = 0;
			}
		}
	}

 

y,x는 dfs에 넣어주는 값입니다. 모든 좌표중에 7개를 선택하는 경우입니다. 즉 25C7입니다.  480,700 가지의 경우의 수이므로 충분히 가능합니다. j = (i == y ? x : 0)는 처음에는 x좌표부터 시작하고 그이후점부터는 0으로 시작한다는 삼항연산자입니다.

 

• 1. 25개 좌표중에 7개 선택하기- dfs
• 2. 7개의 좌표들이 서로 연결되어 있는지 확인하기 - search
• 3. 결과도출

 

아래는 전체코드입니다.

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

int result = 0;
string arr[5];
bool chk[5][5] = { 0, };
bool temp[5][5] = { 0, };
int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };

void search(int y, int x) {
	temp[y][x] = 1;
	for (int i = 0; i < 4; i++) {
		int ny = y + y_ar[i];
		int nx = x + x_ar[i];
		if (chk[ny][nx] == 1 && temp[ny][nx] == 0)
			if (ny >= 0 && ny < 5 && nx >= 0 && nx < 5)
				search(ny, nx);
	}
}

void dfs(int cnt, int y, int x, int som, int yim) {
	if (yim >= 4)
		return;
	if (cnt == 7 && som >= 4) {
		int val_temp = 0;
		memset(temp, 0, sizeof(temp));
		for(int i=0;i<5;i++)
			for(int j=0; j<5;j++)
				if (chk[i][j] == 1&& temp[i][j]==0) {
					search(i, j);
					val_temp++;
				}

		if (val_temp == 1)
			result++;
		return;
	}


	for (int i = y; i < 5; i++) {
		for (int j = (i == y ? x : 0); j < 5; j++) {
			if (chk[i][j] == 0) {
				chk[i][j] = 1;
				dfs(cnt + 1, i, j, arr[i][j] == 'S' ? som + 1 : som, arr[i][j] == 'Y' ? yim + 1 : yim);
				chk[i][j] = 0;
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

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

	dfs(0, 0, 0, 0, 0);

	cout << result << endl;

	return 0;
}