개요

백준 1405: 미친 로봇

• 입력
  첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자연수 또는 0이다. 그리고, 동서남북으로 이동할 확률을 모두 더하면 100이다.

  확률의 단위는 %이다.

• 출력
  첫째 줄에 로봇의 이동 경로가 단순할 확률을 출력한다. 절대/상대 오차는 10-9 까지 허용한다.

접근 방식

1. 백트래킹 방식을 통해 방문하지 않았던 곳으로만 방문하며
   해당 칸으로 이동할 확률을 다 계산해줬다.

2. 백트래킹함수의 매개변수로는 좌표의 행값, 열값, 이동횟수, 해당 좌표까지 이동할 확률을 넣어줬다.

/// @brief 각 좌표에 대해서 확률을 계산해서 N만큼 이동했을 때 해당 확률 ans에 더하는 함수
/// @param height 행좌표
/// @param width 열좌표
/// @param length 이동한 횟수
/// @param percentage 해당 좌표에 올 확률
void Backtracking(int height,int width,int length,double percentage)

3. 다음으로 이동할 좌표를 반복문을 통해 처리를 해줬다.

//좌표 반복문 처리용 0=north, 1=south, 2=west, 3=east
int dh[4] = { -1,1,0,0 };
int dw[4] = { 0,0,-1,1 };
//percentage저장용 배열
double directionPer[4];

void Input() {
	cin >> N >> eastPer >> westPer >> southPer >> northPer;
	directionPer[0] = (double)northPer/100;
	directionPer[1] = (double)southPer/100;
	directionPer[2] = (double)westPer/100;
	directionPer[3] = (double)eastPer/100;
}

Input함수에서 directionPer배열에 확률을 저장해주었다.

	for (int i = 0; i < 4; i++) {
		//다음 조사할 행값
		int nextH = height + dh[i];
		//다음 조사할 열값
		int nextW = width + dw[i];
		//다음 칸으로 갈 확률이 0이면 continue
		if (!directionPer[i]) continue;

Backtracking함수에서 반복문을 통해 다음 좌표를 결정하는 부분이다.

전체 코드

#include<iostream>

using namespace std;
//N, 동쪽 확률, 서쪽 확률, 북쪽 확률, 남쪽 확률
int N = 0, eastPer = 0, westPer = 0, northPer = 0, southPer = 0;
//답
double ans = 0;
//중앙 14,14에서 출발해서 동서남북 어느쪽으로든 14칸 갈 수 있도록 2차원 배열 생성
int field[29][29];
bool visited[29][29];
//좌표 반복문 처리용 0=north, 1=south, 2=west, 3=east
int dh[4] = { -1,1,0,0 };
int dw[4] = { 0,0,-1,1 };
//percentage저장용 배열
double directionPer[4];

void Input() {
	cin >> N >> eastPer >> westPer >> southPer >> northPer;
	directionPer[0] = (double)northPer/100;
	directionPer[1] = (double)southPer/100;
	directionPer[2] = (double)westPer/100;
	directionPer[3] = (double)eastPer/100;
}

/// @brief 각 좌표에 대해서 확률을 계산해서 N만큼 이동했을 때 해당 확률 ans에 더하는 함수
/// @param height 행좌표
/// @param width 열좌표
/// @param length 이동한 횟수
/// @param percentage 해당 좌표에 올 확률
void Backtracking(int height,int width,int length,double percentage) {
	//조건에 도달했을 때,
	if (length == N+1) {
		ans += percentage;
		return;
	}
	//시작점 방문처리
	visited[height][width] = true;

	for (int i = 0; i < 4; i++) {
		//다음 조사할 행값
		int nextH = height + dh[i];
		//다음 조사할 열값
		int nextW = width + dw[i];
		//다음 칸으로 갈 확률이 0이면 continue
		if (!directionPer[i]) continue;
		//방문했다면 continue;
		if (visited[nextH][nextW]) continue;
		//예외문 다 뚫었으면 방문 처리해주고
		visited[nextH][nextW] = true;
		//percentage곱해줌
		percentage *= directionPer[i];
		//그다음 단계 백트래킹 실행
		Backtracking(nextH, nextW, length + 1, percentage);
		//모든곳을 다 방문해봐야하니 return해서 이번 정점 방문여부와 방문한 확률 초기화
		percentage /= directionPer[i];
		visited[nextH][nextW] = false;
	}
}

void Solution() {
	Backtracking(14, 14, 1,1.0f);
	//소숫점뒤 유효숫자 9까지 오차 허용이므로
	cout.precision(9);
	cout << ans;
}

int main() {
	Input();
	Solution();

}

문풀후생

Backtracking함수에서 length가 N일때 percentage를 다 더해줬더니,
이동횟수가 N번째일때 조건을 거르지않고 모든 확률을 다 더해버려서 답이 계속 1이 나왔었다.

따라서 한계값 다음값인 length==N+1일때 더해줘야 length가 N일때도 조건에 걸러져서 답에 맞는 값들만 더해진다.

예제 1번도 처음에 되게 이해가 안 갔었는 데,
문제의 조건을 단순해질 확률로 잘못 보고 동서, 서동, 북남, 남북 해서
0.625 * 4= 0.25가 답이여야되는데 왜 0.75지 하고 한참을 생각했다,,

그리고 좀 창피했던건
답 ans를 double형으로 출력하면 예제 2,3번에서 답이 1.0이 아니라 1이 나온다. 답으로 1.0이 꼭 나와야 하는 줄 알고
Solution함수에서 if(ans==1) cout<<"1.0" 이렇게 문자열로 출력해줬다..
문자열 "1.0"이 정답으로 인식되어서
그 후 그냥 cout<<ans로 1 출력하게 해봤더니 이것도 정답이였다..