[백준 9944] NxM 보드 완주하기 (C++)

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

9944번: NxM 보드 완주하기

1. 주의할 점

- EOF를 입력 받을때까지 수행한다

- 매 TC마다 초기화를 진행한다

- 백트레킹으로 진행하므로 사용을 다 했다면, True->False로 꼭 바꿔준다

 

2. 구현

- Cin>>row>>col을 통해 EOF를 입력 받을때까지 수행한다

- Arr[][]배열을 입력받으면서 Check[][] 배열을 초기화한다

- 만약 공을 놓을 수 있는 자리라면, 해당 자리의 Check[][]값을 True로 설정한 이후, DFS()를 수행하고 DFS()가 끝나면 Check[][]값을 False로 되돌려놓는다

- 4방향 탐색을 통해 해당 방면으로 직진이 가능하면 직진한 이후, Cnt값을 증가시켜서 다음 자리에서 DFS() 함수를 수행한다

- 만약 해당 자리에서 4방향으로 모두 전진이 불가능한 경우, 빈공간에 공이 모두 지나갔는지 확인하며 모두 지나갔다면 Result값과 Cnt를 비교한다

 

#define MAX 1000000
#include <iostream>
#include <algorithm>
using namespace std;
bool check[30][30];
char arr[30][30];
int row, col, result;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

bool can_mv(int y, int x) {
	if (x >= 0 && y >= 0 && x < col && y < row && arr[y][x] != '*' && !check[y][x]) return true;
	return false;
}

void dfs(int y, int x, int cnt) {
	if (cnt >= result) return;
	bool finish = true;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (can_mv(ny,nx)) {
			finish = false;
			check[ny][nx] = true;
			while (1) {
				nx += dx[i];
				ny += dy[i];
				if (can_mv(ny, nx)) 
					check[ny][nx] = true;
				else {
					nx -= dx[i];
					ny -= dy[i];
					break;
				}
			}
			dfs(ny, nx, cnt + 1);
			while (1) {
				if (nx == x && ny == y) break;
				check[ny][nx] = false;
				nx -= dx[i];
				ny -= dy[i];
			}
		}
	}
	if (finish) {
		bool fin = true;
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (arr[i][j] == '.' && !check[i][j]) {
					fin = false;
					break;
				}
			}
			if (!fin) break;
		}
		if (fin) {		
			result = min(result, cnt);
			return;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	string str, buf, s;
	int t = 1;
	while (cin >> row >> col) {
		for(int i=0;i<row;i++)
			for (int j = 0; j < col; j++) {
				cin >> arr[i][j];
				check[i][j] = false;
			}
		result = MAX;
		for (int i = 0; i < row; i++)
			for (int j = 0; j < col; j++) {
				if (arr[i][j] == '.') {
					check[i][j] = true;
					dfs(i, j, 0);
					check[i][j] = false;
				}
			}
		if (result == MAX) result = -1;
		cout << "Case " << t++ << ": " << result << '\n';
	}
	return 0;
}