[백준/BOJ] 백준 9944번 : NxM 보드 완주하기

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

9944번: NxM 보드 완주하기

시작점이 될 수 있는 모든 곳에서 시작하는 것을 고려하여 각 방향으로 가는 경우를 확인해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int n, m;
vector<string> board;
vector<int> result;
int visited[30][30];
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };
int this_result;

void Pre()
{
	board.clear();

	for (int i = 0; i < 30; i++)
		for (int j = 0; j < 30; j++)
			visited[i][j] = 0;

	this_result = 987654321;
}

bool Check()
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			//방문 안한곳이 있을때
			if (visited[i][j] == 0)
				return false;
		}

	return true;
}

int Solve(pair<int, int> here)
{
	if (Check() == true)
		return 0;

	int ret = 987654321;

	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = here;

		//i방향으로 움직일 수 있을때 까지 움직인다
		int cnt = 1;
		while (1)
		{
			there = make_pair(here.first + (dxdy[i][0] * cnt), here.second + (dxdy[i][1] * cnt));

			//there로 움직일 수 있을때
			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m && visited[there.first][there.second] == 0)
			{
				visited[there.first][there.second] = 1;
			}

			//there로 움직일 수 없을때
			else
			{
				//이전 there로 되돌린다
				there = make_pair(there.first - dxdy[i][0], there.second - dxdy[i][1]);

				break;
			}

			cnt++;
		}

		//이동을 했다면
		if (here != there)
		{
			ret = min(ret, Solve(there) + 1);

			//there까지 이동한거 원상복귀
			while (1)
			{
				if (here == there)
					break;

				visited[there.first][there.second] = 0;
				there = make_pair(there.first - dxdy[i][0], there.second - dxdy[i][1]);
			}
		}
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	while (cin >> n >> m)
	{
		Pre();

		for (int i = 0; i < n; i++)
		{
			string input;
			cin >> input;

			for (int j = 0; j < m; j++)
			{
				//장애물은 방문하지 않기 위해 visited에 체크
				if (input[j] == '*')
					visited[i][j] = 1;
			}

			board.push_back(input);
		}

		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
			{
				if (board[i][j] == '.')
				{
					pair<int, int> start = make_pair(i, j);

					visited[start.first][start.second] = 1;
					this_result = min(this_result, Solve(start));
					visited[start.first][start.second] = 0;
				}
			}

		if (this_result == 987654321)
			result.push_back(-1);
		else
			result.push_back(this_result);
	}

	for (int i = 0; i < result.size(); i++)
	{
		cout << "Case " << i + 1 << ": " << result[i] << "\n";
	}

	return 0;
}