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

---

🔗 문제 링크

1405번: 미친 로봇

---

💡 문제 풀이 및 해석

1. 경로가 겹치지 않는 경우만 계산하면 된다.
2. 이 경우보다는 겹칠 때, 이동을 끝내는게 구현에 용이해 보였다.
3. 매번 bool 배열을 파라미터로 받으면 시간초과가 날 수도 있을 것 같아서 전역변수로 방문여부를 체크했다.
4. '1 - 단순하지 않은 경로'로 구현

---

⭐️ 정답 코드 및 설명

#include<iostream>

using namespace std;

int n;
double E, W, S, N;
double answer = 0;
bool isvisit[30][30];
void input() {

    cin >> n >> E >> W >> S >> N;
    E /= 100.0; W /= 100.0; S /= 100.0; N /= 100.0;

}

// 현재 위치에서 다음 위치로 이동할 수 있으면 그 확률을 곱해서 이동
// 이동할 수 없다면 그 상태의 확률에 다음으로 이동하는 확률을 곱해서 answer에 더해줌
// 이동할 수 없는 확률 = 1 - 단순 경로로 이동하는 확률
void gogo(double per, int x, int y, int cnt) {
    if (cnt == n) return; // 이동 횟수가 다되면 끝
    if (!isvisit[y - 1][x]) { 
        isvisit[y - 1][x] = true;
        gogo(per * N, x, y - 1, cnt + 1);
        isvisit[y - 1][x] = false;
    }
    else answer += (per * N);

    if (!isvisit[y + 1][x]) {
        isvisit[y + 1][x] = true;
        gogo(per * S, x, y + 1, cnt + 1);
        isvisit[y + 1][x] = false;
    }
    else answer += (per * S);

    if (!isvisit[y][x + 1]) {
        isvisit[y][x + 1] = true;
        gogo(per * E, x + 1, y, cnt + 1);
        isvisit[y][x + 1] = false;
    }
    else answer += (per * E);

    if (!isvisit[y][x - 1]) {
        isvisit[y][x - 1] = true;
        gogo(per * W, x - 1, y, cnt + 1);
        isvisit[y][x - 1] = false;
    }
    else answer += (per * W);
}

int main() {

    input();

    isvisit[15][15] = true; // 시작점은 항상 방문상태
    gogo(1.0, 15, 15, 0);

    cout.precision(16); // 이거 안한다고 틀리는건 좀..
    cout << 1 - answer;
    return 0;
}

---

🤔 문제 후기

전체적으로 구현하는데 어려움 보다는 단순하지 않은 경로만 구해서 계산한다는 생각을 한 번에 떠올리는 게 어려웠다. 그리고 출력했을 때, 분명히 틀린 부분이 없는데 어디서 틀린걸까? 생각을 하였다. 예제의 출력보다 조금 짧게 나와도 앞부분까지 맞아서 딱히 신경 안썼는데, 문제의 예제 출력이 나오는 부분까지 출력이 안되면 정답이여도 틀렸다고 나와서 cout.precision(16); 를 추가해줬더니 맞게됬다. 앞으로는 이런 부분도 신경써야겠다.