[백준 9207] 페그 솔리테어

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

9207번: 페그 솔리테어

#include <cstdio>
#include <algorithm>
int N;	// 테케 수
char board[5 + 2][9 + 2];
int min_cnt;
int pin_cnt;

int dir_x[4] = { 0, 0, 1, -1 };
int dir_y[4] = { 1, -1, 0, 0 };


void init(void)	// 테케 여러개 이므로 맵과 각 변수들 초기화 필요
{
	for (int i = 0; i < 5; i++) {
		std::fill(board[i], board[i] + 9 + 2, '0');
	}
	min_cnt = 0;
	pin_cnt = 0;
}


void input(void)
{
	for (int i = 0; i < 5; i++) {
		scanf("%s", &board[i]);
		for (int j = 0; j < 9; j++) {
			if (board[i][j] == 'o') pin_cnt++;	// 초기 핀 개수 확인
		}
	}
	min_cnt = pin_cnt;	// 핀을 한 개도 이동하지 않을 때 고려하여 min_cnt를 pin_cnt로 초기화해줌
}



void DFS(int pin_cnt)
{
	min_cnt = (pin_cnt < min_cnt) ? pin_cnt : min_cnt;	// 만약 현재 핀개수가 min_cnt보다 작으면 갱신

	for (int i = 0; i < 5; i++) {		// 어차피 이 for루프가 끝나면 자연스럽게 DFS 함수 종료됨
		for (int j = 0; j < 9; j++) {
			if (board[i][j] == 'o') {	// 해당 좌표에 핀이 있을 때만 고려한다. 
				for (int p = 0; p < 4; p++) {	// 인접한 좌표에 핀이 있어야 한다.  
					int ni = i + dir_x[p];		// 인접 좌표
					int nj = j + dir_y[p];
					int di = ni + dir_x[p];		// 인접 좌표의 다음칸
					int dj = nj + dir_y[p];

					if (ni < 0 || ni > 5 - 1 || nj < 0 || nj > 9 - 1||
						di < 0 || di > 5 - 1 || dj < 0 || dj > 9 - 1) continue;		// 영역을 벗어나면 스루
					if (board[ni][nj] == 'o' && board[di][dj] == '.') {		// 인접 좌표에 핀이 있고, 인접 좌표 다음칸이 비어있다면 핀을 이동할 수 있다. 
						board[i][j] = '.';
						board[ni][nj] = '.';
						board[di][dj] = 'o';
						DFS(pin_cnt - 1);	// 위에서 (ni, nj) 좌표의 핀을 한 개 제거함
						board[i][j] = 'o';	// 다음 경우의 수 탐색을 위해 다시 돌려놓음
						board[ni][nj] = 'o';
						board[di][dj] = '.';
					}
				}

			}
		}
	}
}


int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		init();
		input();
		DFS(pin_cnt);
		printf("%d %d\n", min_cnt, pin_cnt - min_cnt);  // 전체 핀의 개수에서 현재 핀의 개수 뺀 값이 이동 횟수
	}
	return 0;
}

이 문제는 "모든 점을 탐색하면서 핀을 옮길 수 있는지 없는지 탐색"해야 한다. 

따라서 DFS 함수를 콜 할 때 마다 핀이 있는 모든 점을 탐색하면서 1) 인접한 좌표에 핀이 있는지 2) 그 다음 좌표가 비어있는지를 확인하고 핀을 이동시켜 주어야 한다. 

 

DFS(pin_cnt - 1)를 콜 해주고 바꿔준 board의 상태들을 다시 원상복구 해주는 이유는, 다음 번 경우의 수를 탐색하기 위함이다. 

 

또한 출력 시, (전체 핀의 개수 - 남아 있는 핀의 개수)가 최소 이동 횟수가 되는 이유는,  한 번의 이동을 통해 핀을 하나씩 제거하기 때문이다.