[ boj : 17492 ] 바둑알 점프

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

17492번: 바둑알 점프

해설 : 바둑알이 인접한 바둑알을 넘어서면 넘겨진 바둑알은 사라집니다. 이 행위를 반복해서 바둑알을 1개를 만들 수 있냐 없냐를 구하는 문제입니다.

 

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

9207번: 페그 솔리테어

사실 이 문제랑 그렇게 별 차이가 없죠. 굳이 찾으라면 최소인지 아니면 단 한개만 남길 수 있을 것이지 구하는 차이??

 

백트래킹을 사용해서 구해줍시다. 어차피 n의 범위는 10밖에 안되니깐 이중포문을 돌려서 바둑알이 있다면 8방향으로 넘길 수 있는지 체크를 한 후에 넘길수 있으면 지워줄 애들을 지워주고 넘깁니다.

다시 돌아왔을때는 원상태로 만들어줘야겠죠???

 

#include<bits/stdc++.h>

using namespace std;

int n;
int board[10][10];
int dx[] = { -1,-1,0,1,1,1,0,-1 }, dy[] = { 0,1,1,1,0,-1,-1,-1 };
string ans = "Impossible";

void dfs();

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> board[i][j];

	dfs();
	cout << ans;
}
void dfs()
{
	int cnt = 0;

	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if (board[i][j]==2) {
				cnt++;
				for (int d = 0; d < 8; d++) {
					int tx = i + dx[d];
					int ty = j + dy[d];

					if (tx < 0 || tx >= n || ty < 0 || ty >= n)continue;

					if (board[tx][ty] == 2 && board[tx+dx[d]][ty+dy[d]]==0) {
						board[i][j] = 0;
						board[tx][ty] = 0;
						board[tx + dx[d]][ty + dy[d]] = 2;
						dfs();
						board[tx + dx[d]][ty + dy[d]] = 0;
						board[tx][ty] = 2;
						board[i][j] = 2;
					}
				}
			}

	if (cnt == 1) {
		ans = "Possible";
	}
	return;
}