백준(BOJ) 1405번 미친 로봇

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

문제

통제 할 수 없는 미친 로봇이 평면위에 있다. 그리고 이 로봇은 N번의 행동을 취할 것이다.

각 행동에서 로봇은 4개의 방향 중에 하나를 임의로 선택한다. 그리고 그 방향으로 한 칸 이동한다.

로봇이 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. (로봇이 시작하는 위치가 처음 방문한 곳이다.) 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오. 예를 들어, EENE와 ENW는 단순하지만, ENWS와 WWWWSNE는 단순하지 않다. (E는 동, W는 서, N은 북, S는 남)

나의 풀이:

상하좌우로 최대 14번 갈 수 있으므로 MAX를 넉넉히 30으로 잡자.  방문경로를 나타내는 visited 역시 30 * 30 으로 잡아준다

갈수있는 경로로 들어갈때마다 ( 재귀 호출 ) 그때의 확률을 곱해준다. N만큼 방문을 했다면 그 경로는 답에 더해주고 종료한다. 

종료된 후 다음 방문을 위해 visited를 true로 N을 1 증가시켜주는 것을 잊지말자.

코드 ( C ++ )

#include <iostream>

// setprecision 조정자를 위한 헤더 iomanip

#include <iomanip>

using namespace std;

const int MAX = 30;

int N;

int EWNS[4];

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

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

bool visited[MAX][MAX];

double ans;

void solve(int y, int x, double c)

{

// N만큼 다 방문했으면 그때 확률을 더해준다.

if (N == 0) {

ans += c;

return;

}

visited[y][x] = true;

for (int i = 0; i < 4; ++i)

{

int ny = y + dy[i];

int nx = x + dx[i];

if (!visited[ny][nx]) {

N--;

// 동서남북으로 갈 확률에 0.01을 곱해줘서 재귀함수를 호출한다.

solve(ny, nx, c * (EWNS[i]*0.01));

// 다음 방문을 위해 visited를 false로 , N을 1 증가시켜줘서 원래 상태로 복원한다.

visited[ny][nx] = false;

N++;

}

}

}

int main()

{

cin >> N;

for (int i = 0; i < 4; ++i)

cin >> EWNS[i];

solve(15, 15, 1.0);

// 절대/상대 오차 표시 setprecision 조정자

cout << setprecision(10) << ans << "\n";

return 0;

}