BOJ::9207{페그솔테리어};

Infomation

• o: 핀이 꽂혀있는 칸
• #: 구멍이 없는 칸
• .: 빈 칸
  핀의 개수는 최대 8개이며(작은 수로 백트래킹이 가능해 보임),
  
  핀은 수평이나 수직 방향으로 인접한 핀을 뛰어 넘어서 그 핀의 다음 칸으로 이동하는 것만 허용된다.
  
  인접한 핀의 다음 칸은 비어있어야 하며, 인접한 핀은 제거된다.

Idea

1. map의 정보와, 이동 횟수(depth)를 parameter로 갖고 백트래킹을 구현한다.
2. map을 순차적으로 탐색하다가, o를 발견하면 움직일 수 있는 칸이 있는지 확인하고
3. 움직일 수 있다면 이동한 후, 이동한 map의 정보와 depth를 1 추가하고 재귀로 해당 함수를 다시 수행한다.
4. 더이상 이동할 수 없다면, 이동했던 핀을 다시 원래대로 돌려놓고, 다른 핀을 찾기 위해 map을 탐색한다.
5. 이동할 수 있는 다른 핀을 찾게 된다면, 다시 3번으로 돌아가 반복하여 수행한다.
6. 위 과정을 수행하는 도중에 현재 핀의 개수가 최소 개수일 때, 최소값과 depth를 갱신한다.

Code

#include <iostream>
using namespace std;

char map[5][9];
int t, Min = 1e9, Cnt;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

bool IsRange(int x, int y)
{
	return (x >= 0 && y >= 0 && x < 5 && y < 9);
}

void BackTracking(char map[5][9], int depth = 0)
{
	int Cur = 0;
	for (int i = 0; i < 5; ++i) {
		for (int j = 0; j < 9; ++j) {
			if (map[i][j] == 'o') {
				Cur = Cur + 1;
			}
		}
	}

	if (Cur < Min) {
		Min = Cur;
		Cnt = depth;
	}

	for (int x = 0; x < 5; ++x) {
		for (int y = 0; y < 9; ++y) {
			if (map[x][y] == 'o') {

				for (int d = 0; d < 4; ++d) {
					int nx = x + dx[d];
					int ny = y + dy[d];
					int jx = nx + dx[d]; //jump x
					int jy = ny + dy[d]; //jump y

					if (IsRange(nx, ny) && IsRange(jx, jy)
						&& map[nx][ny] == 'o' && map[jx][jy] == '.') {
						map[x][y] = '.';
						map[nx][ny] = '.';
						map[jx][jy] = 'o';
						BackTracking(map, depth + 1);
						map[x][y] = 'o';
						map[nx][ny] = 'o';
						map[jx][jy] = '.';
					}
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin >> t;

	while (t--) {
		for (int i = 0; i < 5; ++i) {
			for (int j = 0; j < 9; ++j) {
				cin >> map[i][j];
			}
		}

		BackTracking(map);

		cout << Min <<" "<< Cnt << "\n";
		Min = 1e9;
		Cnt = 0;
	}
}