질문 합니다

  • cocogod
    cocogod

    JUMPGAME
    이 문제를 BFS로 풀어보려고 합니다.
    0,0 에서 시작하여
    오른쪽이나 아랫쪽으로만 점프를 하며
    n-1,n-1으로 도달할수 있는지만 확인하면 되므로
    쉽게 풀릴거라 생각하는대 오답으로 나오내요 ..?

    한번 확인부탁드립니다 .

    #include <cstdio>
    #include <iostream>
    #include <queue>
    #include <algorithm>
    #include <string.h>
    #include <stack>
    
    using namespace std;
    int n;
    int ddang[101][101];
    
    bool bfs(int r,int c){
    
        bool visited[101][101];
        memset(visited,false,sizeof(visited));
        visited[r][c] = true;
        queue<pair<int,int> > q;
        q.push(make_pair(r,c));
    
        while(!q.empty()){
            int r = q.front().first;
            int c = q.front().second;
            q.pop();
            if(r == n-1 && c== n-1)
                return true;
    
            int jump = ddang[r][c] ;
            if( r+jump >=0 && r+jump < n && c >=0 && c< n){
                if(visited[r+jump][c] )
                    continue;
                visited[r+jump][c]= true;
                q.push(make_pair(r+jump , c));
            }
            if( r >=0 && r < n && c+jump >=0 && c+jump < n){
                if(visited[r][c+jump] )
                    continue;
                visited[r][c+jump]= true;
                q.push(make_pair(r , c+jump));
            }
    
        }
        return false;
    }
    
    int main(){
        int t;
        cin >> t;
        while(t--){
            scanf("%d",&n);
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    scanf("%d",&ddang[i][j]);
                }
            }
    
            printf("%s\n",bfs(0,0) ? "YES" : "NO");
    
        }
    }
    

    5년 전
1개의 댓글이 있습니다.
  • Arine
    Arine

    1
    5
    1 1 1 1 1
    1 1 9 9 1
    1 9 9 9 1
    9 9 9 9 1
    9 9 9 9 0

    위와 같은 반례가 있습니다. 사소한 실수 때문이지만, 왜 이런 반례가 생겼는지 직접 찾아보시는 것도 재밌을 것 같아요.


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