[C++] 백준 1405번: 미친 로봇

문제 링크

1405번: 미친 로봇

문제 요약

동서남북으로 움직일 수 있는 로봇이 있다. 로봇이 각 방향으로 갈 확률이 주어질 때, 이 로봇이 같은 장소를 재방문하지 않고 N번 이동할 수 있을 확률을 구하여라

접근 방법

N이 14인데, 방향은 4이기 때문에, 4개 방향에 대해서 N까지 완전탐색을 다 돌려준 다음에 경로를 확인해보면 시간초과가 날 수도 있습니다. $4^{14}=268435456$인데 문제의 제한시간은 1초입니다.

따라서 상태공간트리를 탐색하면서 동서, 남북 방향으로 방문하는 위치를 저장하고, 재방문 하는 경우에는 바로 가지를 쳐줘야 합니다. 그리고 N번까지 움직였을 때만 결과에 확률을 더해주면 됩니다.

std::set으로 풀었던 느린 코드(AC)

#include <bits/stdc++.h>

using namespace std;

int n, dir[4][2] = { {0, 1}, {0, -1}, {-1, 0}, {1, 0} };
set<pair<int, int>> s;
double p[4], res;

void func(int cnt, int y, int x, double val)
{
	if (cnt == n)
	{
		res += val;
		return;
	}

	for (int i = 0; i < 4; i++)
	{
		int ny = y + dir[i][0], nx = x + dir[i][1];
		if (s.find({ ny, nx }) == s.end() && p[i] != 0)
		{
			s.insert({ ny, nx });
			func(cnt + 1, ny, nx, val * p[i]);
			s.erase({ ny, nx });
		}
	}
}

int main(void)
{
	cin >> n;
	for (int i = 0; i < 4; i++)
		cin >> p[i], p[i] *= 0.01;

	s.insert({ 0, 0 });
	func(0, 0, 0, 1);
	cout << fixed;
	cout.precision(10);
	cout << res;
	return 0;
}

처음에는 std::set을 이용해서 재방문을 체크해주는 식으로 풀었는데, AC를 받기는 했지만 C++로 푼 다른 분들 대비 10배 이상 느리게 시간이 나왔습니다. 어차피 N이 최대 14고 한 방향으로만 이동해도 14번만 이동하는 것이기 때문에, bool형의 2차원 배열의 중간에서 시작하는 식으로 다시 한 번 풀어줬습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int n, dir[4][2] = { {0, 1}, {0, -1}, {-1, 0}, {1, 0} };
bool visited[40][40];
double p[4], res;

void func(int cnt, int y, int x, double val)
{
	if (cnt == n)
	{
		res += val;
		return;
	}

	for (int i = 0; i < 4; i++)
	{
		int ny = y + dir[i][0], nx = x + dir[i][1];
		if (!visited[ny][nx] && p[i] != 0)
		{
			visited[ny][nx] = true;
			func(cnt + 1, ny, nx, val * p[i]);
			visited[ny][nx] = false;
		}
	}
}

int main(void)
{
	cin >> n;
	for (int i = 0; i < 4; i++)
		cin >> p[i], p[i] *= 0.01;

	visited[20][20] = true;
	func(0, 20, 20, 1);
	cout << fixed;
	cout.precision(10);
	cout << res;
	return 0;
}