[ 백준 1405 ] 미친 로봇 (C++)

[문제보기]

 

[해결과정]

<사진> 문제 이해가 안될 경우 참고

 

 1. input : n, double 형 d[4] ( 동, 서, 남, 북 )

   -> d[i]/=100으로 해서 소수점으로 변환

 

 2. 동, 서, 남, 북으로 이동하는 것을 맵에서 check 하기 위해서 map배열을 만들어준다.

   -> 맵의 가장 중앙 지점을 방문 처리 한다.

 

 3. 맵의 가장 중앙 지점 부터 dfs 실행

   -> dfs(y,x, cnt, p) cnt는 dfs count이고, p는 확률(소수)를 담을 변수

   -> 만약, 단순한 경로(겹치지 않는 경로) 일 경우 ret += p

      -> 현재까지의 확률을 정답란에 저장

   -> 만약, 단순한 경로가 아닌 경우(이미 방문한 지점을 방문) 패스

 

 4. output : 소수점 11자리 까지 지정하여 출력

  -> cout.precision(11); cout.fixed; 사용

 

 

[소스코드]

/*
    BOJ 1405 - 미친 로봇
    Created by haejun on 2020/02/26
*/
#include<iostream>
#include<vector>
#include<queue>
#include<memory.h>
#include<math.h>
#include<algorithm>
using namespace std;
 
int n;
bool arr[100][100];
double d[4];
double ret;
 
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
void dfs(int y, int x, int cnt, double p) {
    if (cnt == n) {
        ret += p;
        return;
    }
 
    int ny, nx;
    for (int i = 0; i < 4; i++) {
        ny = y + dy[i];
        nx = x + dx[i];
        if (arr[ny][nx] == 0) {
            arr[ny][nx] = 1;
            dfs(ny, nx, cnt + 1, p * d[i]);
            arr[ny][nx] = 0;
        }
    }
}
 
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < 4; i++) {
        cin >> d[i];
        d[i] /= 100;
    }
 
 
    arr[50][50] = 1;
    dfs(50,50,0,1);
 
    cout.precision(11);
    cout.fixed;
    cout << ret << "\n";
    
 
    return 0;
}

[해결 과정 중 실수한 부분]

 이게 무슨 문제인지, 이해하는데 한참 걸렸다;.. 단순하게, DFS를 하는게 겹치지 않고 모든 경우를 수행했을 경우, 그동안 진행했던 동서남북의 확률들을 더해,, 그 값을 출력하는 문제였다........

 

 문제 해석 능력이,,,,,,,, 현저히 떨어진다는 것을 느꼈다. 나름 고등학교 문과 출신인데 ㅠㅠ

 

 

[관련 문제 혹은 비슷한 문제]

 DFS