[백준 9207] 페그 솔리테어 (C++)

문제 링크: https://www.acmicpc.net/problem/9207

9207번: 페그 솔리테어

1. 주의할 점

- 백트레킹을 통해서 구현한다(핀의 최대 개수: 8)

- 맵을 바꾼 후, 다시 돌아왔을 때 맵을 복구하는 과정이 필요하다

 

2. 구현

- DFS를 통해 백트레킹 방식으로 구현한다.

- 맵의 크기가 5X9밖에 되지 않으므로 매번 전부 확인한다. Arr[i][j]의 값이 'o'이라면 인접한칸과 인접한칸 다음의 칸을 살핀다.

- Back_tracking() 함수의 마지막에 현재 배열에 남아있는 'o'의 개수를 구한다.

- 결과는 Result(남아있는 'o'의 최솟값), 기존에 있던 'o'의 갯수 - Result를 출력한다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
char arr[5][9];
int result, pin;

void back_tracking() {
	for (int i = 0; i < 5; i++) {
		for (int j = 0; j < 9; j++) {
			if(arr[i][j]=='o'){
				for (int k = 0; k < 4; k++) {
					int nx = j + dx[k];
					int ny = i + dy[k];
					if (nx >= 0 && ny >= 0 && nx < 9 && ny < 5 && arr[ny][nx] == 'o') {
						int nnx = nx + dx[k];
						int nny = ny + dy[k];
						if (nnx >= 0 && nny >= 0 && nnx < 9 && nny < 5 && arr[nny][nnx] == '.') {
							arr[nny][nnx] = 'o';
							arr[ny][nx] = '.';
							arr[i][j] = '.';
							back_tracking();
							arr[nny][nnx] = '.';
							arr[ny][nx] = 'o';
							arr[i][j] = 'o';
						}
					}
				}
			}
		}
	}
	int temp = 0;
	for (int i = 0; i < 5; i++) 
		for (int j = 0; j < 9; j++) 
			if (arr[i][j] == 'o') 
				temp++;
	result = min(result, temp);
}

int main() {
	int test;
	cin >> test;
	for (int t = 0; t < test; t++) {
		result = 9;
		pin = 0;
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 9; j++) {
				cin >> arr[i][j];
				if (arr[i][j] == 'o') pin++;
			}
		back_tracking();
		cout << result << " " << pin - result << '\n';
	}
	system("pause");
	return 0;
}