백준(BOJ) 9944번 NxM 보드 완주하기

문제 : https://www.acmicpc.net/problem/9944

9944번: NxM 보드 완주하기

 

풀이 :

 

완전 탐색을 이용하여 각 공이 될수 있는 지점마다 재귀호출을 통해 구하자. 선택된 각 지점에서는 상하좌우

 

방향으로 쭉 가면서 '.' 인 지점을 모두 방문하여야 종료하게 된다.

 

코드 ( C++ )

 

	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>
	using namespace std;
	const int dy[4] = { 1,-1,0,0 };
	const int dx[4] = { 0,0,1,-1 };
	string board[31];
	int n, m;
	int visited[31][31];
	bool check(int y, int x)
	{
	if (y >= 0 && y < n && x >= 0 && x < m)
	return true;
	return false;
	}
	int solve(int y, int x, int num)
	{
	if (num == 0) {
	return 0;
	}
	int ret = -1;
	for (int i = 0; i < 4; ++i)
	{
	int ny = y + dy[i];
	int nx = x + dx[i];
	while (check(ny,nx) && !visited[ny][nx] && board[ny][nx] == '.')
	{
	num--;
	visited[ny][nx] = true;
	ny += dy[i];
	nx += dx[i];
	}
	ny -= dy[i];
	nx -= dx[i];
	if (ny != y || nx != x) {
	int cand = solve(ny,nx,num);
	if (cand != -1) {
	if (ret == -1 || ret > cand+1) {
	ret = cand+1;
	}
	}
	}
	//돌려놓기
	while (ny != y || nx != x) {
	visited[ny][nx] = false;
	num++;
	ny -= dy[i];
	nx -= dx[i];
	}
	}
	return ret;
	}
	int main()
	{
	int cnt = 1;
	while (cin >> n >> m) {
	int num = 0;
	for (int i = 0; i < n; ++i) {
	cin >> board[i];
	for (int j = 0; j < m; ++j) {
	if (board[i][j] == '.')
	num++;
	}
	}
	int ret = -1;
	for(int i=0; i<n; ++i)
	for (int j = 0; j < m; ++j)
	{
	if (board[i][j] == '.') {
	visited[i][j] = 1;
	int cand = solve(i, j, num-1);
	if (cand != -1) {
	if (ret == -1 || ret > cand) {
	ret = cand;
	}
	}
	visited[i][j] = 0;
	}
	}
	cout << "Case " << cnt << ": " << ret << "\n";
	cnt++;
	}
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub