JUMPGAME 도저히 어디가 틀린건지 모르겠습니다..

  • int_solution
    int_solution
    #include <stdio.h>
    
    bool arr_true[101][101];    // 점에 다시 방문해도 될지를 결정
    int arr[101][101],flag=0;
    void jump(int n, int k,int max)
    {   // 재귀로 모든 경로를 탐색
        if(arr_true[n][k] == false || n > max || k > max || flag==1) return ;   // 만약 범위를 넘어가거나 끝까지 갈 수 있는 경우(flag==1) return
        if(n == max && k == max) flag=1;    // 찾은 경우 flag=1 로 초기화
        jump(n,k+arr[n][k],max);    // 오른쪽 경로 탐색
        jump(n+arr[n][k],k,max);    // 왼쪽 경로 탐색
        if(flag==0) arr_true[n][k]=false;   // 오른쪽, 왼쪽을 모두 탐색했음에도 찾지 못한 경우 이 원소는 더 이상 탐색x(false로 초기화)
    }
    int main(void)
    {
        int c;
        scanf("%d",&c);
        while(c--)
        {
            int n,i,j;
            scanf("%d",&n);
            for(i=0;i<n;i++)
            {
                for(j=0;j<n;j++)
                {
                    scanf("%d",&arr[i][j]);
                    arr_true[i][j] = true;  // 쓸 점들은 모두 true로 초기화
                }
            }
            jump(0,0,n-1);  // 함수 콜
            if(flag==1) printf("Yes\n");
            else printf("No\n");
            flag=0;
            for(i=0;i<100;i++) for(j=0;j<100;j++) arr_true[i][j]=true;  // 모두 다시 true로 초기화
        }
        return 0;
    }
    

    처음에 백트랙킹으로 모든 경로를 다 돌았는데 시간 초과가 났습니다.. 조금 생각 해보니까중복되는 경로(다시 방문할 수도 있는 점)가 있겠구나 싶어서 저렇게 구분을 해놓았는데 계속 틀렸다고 나오네요.. 어디가 오류가 되는건지 모르겠습니다.. ㅠ


    10년 전
2개의 댓글이 있습니다.
  • nailbrainz
    nailbrainz

    음..
    의외의 곳에서 틀렸을 수도 있지 않을까요?? 맞다고 채점되기 위해선 정확해야 하는 그런 부분..


    10년 전 link
  • rhearic
    rhearic

    출력 부분을 정확히 맞춰주시면 되겠습니다..


    9년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.