글 읽기 - 이렇게 푸는거 아닌가요??

plzrun 8년 전 0

bfs로 돌렸는데 틀렸다고 뜹니다. 어디가 틀린건가요 ㅠ?

di[]배열은 방향을 의미합니다. dx[], dy[]를 정의할때 순서대로 동, 서, 남, 북을 향하도록 집어넣었기 때문에

di[]배열 또한 순서대로 동, 서, 남, 북으로 가는 확률을 의미합니다. (25를 입력으로 받으면 0.25가 저장되도록 했어요)

그리고 bfs돌면서 check된 부분(방문한 부분)에 닿으면 그냥 넘어가는거고... 방문 안한곳으로 가면 이전까지 구했던 해당 경로에 대한 확률값(pr)과 di[] 배열을 곱해서 해당 경로에 대한 확률값을 갱신합니다.

그리고 cnt값이 n값에 다다르면 그 경로가 끝까지 다 가봤다는 게 되고 그 확률값을 ans 변수에 더해줍니다.

#include <stdio.h>
#include <queue>
#include <cstring>
using namespace std;
bool chk[29][29];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int n;
double ans=0, p=0, di[4];
struct Info{
    int x, y;
    double pr;
    Info(int xx, int yy, double ppr) {
        x=xx; y=yy; pr=ppr;
    }
};
queue<Info> q;
void bfs(int x, int y, double pr) {
    q.push(Info(x,y,pr));
    int cnt = 0;
    while(!q.empty()) {
        int sz = q.size();
        for(int t=0; t<sz; t++) {
            Info in=q.front(); q.pop();
            chk[in.x][in.y] = true;
            if(cnt >= n) {
                ans+=in.pr;
                continue;
            }
            int nx, ny;
            for(int i=0; i<4; i++) {
                nx = in.x+dx[i];
                ny = in.y+dy[i];
                if(chk[nx][ny]) continue;
                q.push(Info(nx,ny,in.pr*di[i]));
            }
        } cnt++;
    }
}
int main() {
    memset(chk, false, sizeof(chk));
    scanf("%d", &n);
    for(int i=0; i<4; i++) {
        scanf("%lf", &di[i]);
        di[i]/=100;
    }
    chk[n][n] = true;
    bfs(n,n,1);
    printf("%.10lf", ans);
    return 0;
}

yukariko 8년 전 3

체크르 방문하기 전에 처리하지 않고 방문할때 처리하면 중복이 발생할 수 있습니다.

plzrun 8년 전 0

답변 감사합니다 ㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이렇게 푸는거 아닌가요??

plzrun 8년 전 0

yukariko 8년 전 3

plzrun 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말