[백준,c++] 1405번 - 미친 로봇

문제

1405번: 미친 로봇

 

코드

#include <iostream>
using namespace std;

int N,a,b,c,d;

int map[31][31];
int visited[31][31];

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

double percent[4],out=0.0;



void dfs(int depth, int x, int y,double ans){
    visited[x][y]=1;
    
    if(depth==N){
        out += ans;
        return;
    }
    
    for(int i=0; i<4; i++){
        if(percent[i]==0) continue;
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(!visited[nx][ny]&&percent[i]!=0){
            visited[nx][ny]=1;
            dfs(depth+1,nx,ny,ans*percent[i]);
            visited[nx][ny]=0;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>N;
    for(int i=0; i<4; i++){
        double inp; cin>>inp;
        percent[i] = inp/100.0;
    }
    
    dfs(0,14,14,1); //  시작점이 14,14 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    
    cout.precision(11);
    cout << fixed<<out;
}

 

풀이

처음 문제를 이해하는데 조금 시간이 걸렸다. 문제에서 말하는 이동 경로가 단순 하다 라는 조건은 동일한 곳을 방문하지 않는 경로를 말한다. 즉 EE는 오른쪽으로 두번가서 겹치지 않는 길이라 단순하고, EW는 오른쪽으로 갔다가 왼쪽으로 오면 한번 방문했던 곳을 겹치기 때문에 단순하지 않은 경로가 된다.

inp: 2 25 25 25 25

위와 같은 입력이 들어올때 갈 수 있는 경우의 수는

• EE:  0.25*0.25
• EW // 단순하지 않은 경로
• ES: 0.25*0.25 =0.0625
• EN: 0.25*0.25
• WW: 0.25*0.25
• WE // 단순하지 않은 경로
• WS: 0.25*0.25
• WN: 0.25*0.25
• SS: 0.25*0.25
• SE:  0.25*0.25
• SW: 0.25*0.25
• SN // 단순하지 않은 경로
• NN: 0.25*0.25
• NE:  0.25*0.25
• NW: 0.25*0.25
• NS // 단순하지 않은 경로

위와 같은데, (0.25*0.25)*3*4=0.75라는 output이 나온다. 

처음에 확률인데 0.25+0.25 로 더하는 로직을 짜서 틀렸다; 

 

추가로 탐색의 시작점은 중앙값인 (14,14) 이다.. (0,0)으로 시작해서 계속 틀렸었다.. 문제를 잘 읽자..